# 题解：HDU6629 String Mathching

### Problem Description

String matching is a common type of problem in computer science. One string matching problem is as following:

Given a string S[0\cdots len−1], please calculate the length of the longest common prefix of S[i\cdots len−1] and S[0 \cdots len−1] for each i>0.

I believe everyone can do it by brute force.
The pseudo code of the brute force approach is as the following:

We are wondering, for any given string, what is the number of compare operations invoked if we use the above algorithm. Please tell us the answer before we attempt to run this algorithm.

### input

The first line contains an integer T, denoting the number of test cases.
Each test case contains one string in a line consisting of printable ASCII characters except space.

• 1 \leq T \leq 30

• string length \leq 106 for every string

### Output

For each test, print an integer in one line indicating the number of compare operations invoked if we run the algorithm in the statement against the input string.

### Sample Input

 3
_Happy_New_Year_
ywwyww
zjczzzjczjczzzjc


### Sample Output

17
7
32


KMP算法讲解传送门：🚪

## AC代码

#include <bits/stdc++.h>
using namespace std;
int nexts[1000006];
char T[1000006];
long long ans = 0;
void getNext(){
int m = strlen(T);
// m:T的长度
int a = 0, p = 0;
for (int i = 1; i < m; i++) {
if (i >= p || i + nexts[i - a] >= p) {
if (i >= p) p = i;
while (p < m && T[p] == T[p - i])
p++;
nexts[i] = p - i;
if(i + nexts[i] >= m)
ans += nexts[i];
else ans += nexts[i] + 1;
a = i;
}
else{
nexts[i] = nexts[i - a];
if(i + nexts[i] >= m)
ans += nexts[i];
else ans += nexts[i] + 1;
}
}
}
int main(){
int n;
scanf("%d", &n);
while(n--){
scanf("%s", T);
ans = 0;
getNext();
printf("%lld\n", ans);
}
return 0;
}


Not Comment Found