Compare string - MarisaOJ: Marisa Online Judge

Given a function

f (s, t)

$f(s, t)$ which takes two string

s

$s$ and

t

$t$ as input. Without loss of generality that

| s | \leq | t |

$|s| \le |t|$ , let's say the output of the function is as follow:

f (s, t) = {\begin{cases} 0, & if s is a prefix of t . \\ the first position where s and t differ, & otherwise . \end{cases}

$\begin{equation} f(s, t)=\begin{cases} 0, & \text{if $s$ is a prefix of $t$}.\\\\ \text{the first position where $s$ and $t$ differ}, & \text{otherwise}. \end{cases} \end{equation}$ For example,

f (abc, abd) = 3

$f(\text{abc}, \text{abd}) = 3$ . Given a

n

$n$ string

S_{i}

$S_i$ . Calculate:

\sum_{i = 1}^{n} \sum_{j = i + 1}^{n} f (S_{i}, S_{j})

$\sum_{i=1}^{n} \sum_{j=i+1}^{n} f(S_i,S_j)$ ### Input - The first line contains an integer

n

$n$ . - The next

n

$n$ lines, each line contains a string

S_{i}

$S_i$ , each string contains only lowercase letters. ### Output - Print the value. ### Constraints -

1 \leq n \leq 10^{5}

$1 \le n \le 10^5$ . -

1 \leq \sum | S_{i} | \leq 10^{6}

$1 \le \sum{|S_i|} \le 10^6$ ### Example Input:

4 c a t \hat{m} a t s i r

$4 cat hat mat sir$

Output:

6

$6$

Introduction to Trie
	Prefix
	Compare string
	Maximum score
	Report
	Maximum XOR subarray
	Query on string
	Language
	Poem
	Palindrome pairs
	Mass XOR queries
	XOR-path on tree
	The ancient book

Topic

Data structure

String

Rating

1300

Solution (0)

Solution