hdu 4513 KMP里next数组的运用

浏览数：30 / 时间：2015年06月08日


这道题不难   前提是搞懂next数组的求的过程        加上点递归的思想  


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

char str[200021];
int main()
{
    int n,i,j,T;
    int next[200020];
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        scanf("%s",str);
        str[n]=‘@‘;
        n++;
        memset(next,0,sizeof(next));
        next[0]=-1;
        int sum=0,j=0,k=-1;
        while(j<n)
        {
            if(k==-1||str[j]==str[k])
            {
                ++k;
                ++j;
                next[j]=k;
            }
            else k=next[k];
        }
        sum=0;
        for(i=1;i<n;i++)
        {
            sum++;
            int k=i;
            while(next[k])
            {
                sum++;
                sum%=10007;
                k=next[k];
            }
        }
        printf("%d\n",sum);
    }
    return 0;
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

标签： 编程语言 Java C C# Javascript js Python Ruby Spring 程序 VB

相关文章

随机文章

您可能还喜欢

您可能还喜欢