学步园

hdu3336一样的题目

kmp+dp可以做.

队友的思路，开一个数组记录与前一个字符相等的下表，

每次只需比较与上个字符相等下表+1的字符是否相等

#include<stdio.h>
#include<string.h>
int a[100001];
int main()
{
	int i,j,k,p,len;
	char s[100001];
	while(scanf("%s",s)!=-1)
	{
		len=strlen(s);
		int sum=len;
		j=0;
		for(i=1;s[i];i++)
			if(s[i]==s[0])
			   a[j++]=i;
		sum+=j;
		for(i=1;s[i];i++)
		{
			for(p=0,k=0;k<j&&k+1<len;k++)
				if(s[a[k]+1]==s[i])
					a[p++]=a[k]+1;
				sum+=p;j=p;
		}
		printf("%d\n",sum%256);
	}
	return 0;
}

KMP+Dp

#include<stdio.h>
#include<string.h>
#define N 100010
int dp[N],next[N],n;
char s[N];
void get()
{
    next[1]=0;
    int i,j=0;
    for(i=2;i<=n;i++)
    {
        while(j>0&&s[i]!=s[j+1])
            j=next[j];
        if(s[i]==s[j+1])
            j++;
        next[i]=j;
    }
}
int main()
{
    int i,j;
    while(scanf("%s",s+1)!=-1)
    {
        n=strlen(s+1);   
        get();
        dp[0]=0;
        int sum=0;
        
        for(i=1;i<=n;i++)
        {
            //printf("%d ",next[i]);
            dp[i]=(dp[next[i]]+1)%256;
            sum=(sum+dp[i])%256;
        }
        printf("%d\n",sum);
    }
    return 0;
}