HDU 3336 Count the string KMP

1662 단어 String
제목 주소: http://acm.hdu.edu.cn/showproblem.php?pid=3336
만약 당신 이 ACMer 라면 클릭 해 보 세 요.
제목: 모든 접두사 가 모 열 에 나타 나 는 횟수 의 총 계 를 구하 십시오.
AC 코드:
 
#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <string>

#include <vector>

#include <list>

#include <deque>

#include <queue>

#include <iterator>

#include <stack>

#include <map>

#include <set>

#include <algorithm>

#include <cctype>

using namespace std;



typedef long long LL;

const int N=200005;

const LL II=100000000;

const int INF=0x3f3f3f3f;

const double PI=acos(-1.0);



int next[N],c[N],ans,len;

char str[N];



void getNext(char *p)

{

    memset(c,0,sizeof(c));

    int j=0,k=-1;

    next[0]=-1;ans=0;

    while(j<len)//len p   

    {

        if(k==-1||p[j]==p[k])

        {

            if(k!=-1)

            {

                c[j]=c[k]+1;

                ans+=c[j];

            }

            j++;

            k++;

            next[j]=k;

        }

        else

            k=next[k];

    }

}



int main()

{

    int i,j,T;

    cin>>T;

    while(T--)

    {

        scanf("%d%s",&len,str);

        getNext(str);

        printf("%d
",(ans+len)%10007); } return 0; }

 

좋은 웹페이지 즐겨찾기