「 HDOJ P3336 」 Count the string

Subject matter

Given a string of $s$which is $n in length, you are asked to find the sum of the times each prefix of $s$appears in $s$. $n\le 200000$.

The idea of solving the problem

The violence prefix each prefix and match the number of occurrences.

That certainly won’t work. The complexity is $O (n\ times (m + n) $and we don’t have to worry about TLE, but let’s consider the nature of the $next $array in $KMP $for each prefix and the longest common substring for each prefix.

That doesn’t mean that if $next [i] = J $then the two substrings of $1 right arrow J $and $i-next [i] + 1 right arrow I $in $s $are equal. It also represents $1.The prefix of \rightarrow j$appears more frequently than $1$.

That’s easy to handle. We only need to find out the $next$array of $s$, and then we can calculate the number of occurrences of the prefix. But it is important to note that $next$can not directly figure out the number of occurrences. Because the $next$array stores the location. So we need to push it step by step.It’s easy to get a recursive formula of $f [i] = f [nxt [i] + 1 $and get the answer by the last count.

Put the code on

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn = 2e5+3, HA = 1e4+7;
int T, p, Ans, nxt[maxn], dp[maxn], n;
char s[maxn];
inline void Getnext() {
    for(int i=2; i<=n; i++) {
        p = nxt[i-1];
        while(p && s[p+1] != s[i]) p = nxt[p];
        if(s[p+1] == s[i]) nxt[i] = p+1;
        else nxt[i] = 0;
    }
}
int main() {
    scanf("%d", &T);
    while (T--) {
        memset(nxt, 0, sizeof(nxt));
        memset(dp, 0, sizeof(dp));
        Ans = 0;
        scanf("%d", &n);
        scanf("%s", s+1);
        Getnext();
        dp[0] = 0;
        for(int i=1; i<=n; i++) {
            dp[i] = dp[nxt[i]] + 1;
            dp[i] = dp[i] % HA;
        }
        for(int i=1; i<=n; i++)
            Ans = (Ans % HA + dp[i] % HA) % HA;
        printf("%d\n", Ans);
    }
}