字符串---KMP

求模式串在目标串中出现的次数和位置

next数组的一些性质

KMP最小循环节、循环周期：
定理：假设S的长度为len则S存在最小循环节，对S构造next数组，循环节的长度L为len-next[len]，子串为S[0…len-next[len]-1]。
（1）如果len可以被len - next[len]整除，则表明字符串S可以完全由循环节循环组成，循环周期T = len/L。
（2）如果不能，说明还需要再添加几个字母才能补全。需要补的个数是循环个数L-len%L = L-(len-L)%L = L-next[len]%L，L = len-next[len]。

代码

namespace KMP{
    int next[10010];
    // 处理模式串的next数组,x[i-next[i]...i-1] == x[0....next[i]-1]
    void kmp_pre(char x[], int m, int _next[]){
        int i, j;
        j = _next[0] = -1;
        i = 0;
        while(i < m){
            while(-1 != j && x[i] != x[j]) j = _next[j];
            _next[++i] = ++j;
        }
    }
    // 改进next数组,减少回溯次数，但不能使用next的性质
    void kmp_pre_2(char x[], int m, int fast_next[]){
        int i, j;
        j = fast_next[0] = -1;
        i = 0;
        while(i < m){
            while(-1 != j && x[i] != x[j]) j = fast_next[j];
            if(x[++i] == x[++j]) fast_next[i] = fast_next[j];
            else fast_next[i] = j;
        }
    }
    //模式匹配,返回出现次数，x模式串，y主串
    int kmp(char x[], int m, char y[], int n){
        int i, j;
        int ans = 0;
        kmp_pre(x, m, next);
        //kmp_pre_2(x, m, next);
        i = j = 0;
        while(i < n){
            while(-1 !=j && y[i] != x[j]) j = next[j];
            i++; j++;
            if(j >= m){
                ans++;
                //i-m即为模式串在主串中的开始位置
                j = next[j];
            }
        }
        return ans;
    }
}

例题

hdu3336 next数组+dp
大意：给你个字符串如abab，它的子串a，ab，aba，abab出现次数
即2+2+1+1=6
dp[i]表示以第i个字符结尾的子串出现次数
dp[i] = dp[next[i]] + 1
对于abab，next[]={-1,0,0,1,2}
当i=1时，表示子串a，dp[1] = dp[next[1]] + 1 = dp[0] + 1 = 1，‘a’
当i=2时，表示子串ab，dp[2] = dp[next[2]] + 1 = dp[0] + 1 = 1，'ab'
当i=3时，表示子串aba，dp[3] = dp[next[3]] + 1 = dp[1] + 1 = 2，'a','aba'
当i=4时，表示子串abab，dp[4] = dp[next[4]] + 1 = dp[2] + 1 = 2，'ab','abab'
以a结尾的有'a','a','aba';
以a结尾的有'ab','ab','abab';

#include <stdio.h>
#include <string.h>
#define mem(x,y) memset(x,y,sizeof(x))
const int mod = 10007;
namespace KMP{
    int next[200001];
    // 处理模式串的next数组,x[i-next[i]...i-1] == x[0....next[i]-1]
    void kmp_pre(char x[], int m, int _next[]){
        int i, j;
        j = _next[0] = -1;
        i = 0;
        while(i < m){
            while(-1 != j && x[i] != x[j]) j = _next[j];
            _next[++i] = ++j;
        }
    }
}
int t,n;//200000
char str[200001];
int dp[200001];
int main(){
    scanf("%d",&t);
    while(t--){
        mem(KMP::next,0);
        scanf("%d",&n);
        scanf("%s",str);
        KMP::kmp_pre(str,n,KMP::next);
        int ans=0;
        mem(dp,0);
        for(int i=1;i<=n;i++){
            dp[i] = (dp[KMP::next[i]]+1)%mod;
            ans = (ans + dp[i])%mod;
        }
        printf("%d\n",ans );
    }
    return 0;
}