hdu 3336 Count the string（思维可水过，KMP）

题目

以下不是KMP算法——

以下是kiki告诉我的方法，好厉害的思维——

就是巧用标记，先标记第一个出现的所有位置，然后一遍遍从标记的位置往下找。

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

int main()
{
    int xin,t,i,j,n,ans,id,xiabiao[200010],shunxu;
    char ch[200010];
    scanf("%d",&t);
    while(t--)
    {
        
        memset(xiabiao,0,sizeof(xiabiao));
        scanf("%d",&n);
        scanf("%s",ch);
        id=0;shunxu=0;
        ans=0;
        for(j=0;j<n;j++)
        {
            if(ch[j]==ch[shunxu])
                xiabiao[id++]=j;
        }
        ans+=id;
        ans=ans%10007;
        do
        {
            shunxu++;
            xin=0;
            for(i=0;i<id;i++)
            {
                if(xiabiao[i]+1<n)
                {
                    if(ch[xiabiao[i]+1]==ch[shunxu])
                    {
                        xiabiao[xin++]=xiabiao[i]+1;
                    }
                }
            }
            ans+=xin;
            ans=ans%10007;
            id=xin;
        }while(shunxu<n-1);
        printf("%d
",ans);
    }
    return 0;
}