hdu 3336

本來以為是ＫＭＰ，後來想起以前看過的一片文章，只需要記錄滿足情況的此時位置的下一個的下標，然後下次比較就從從此進行比較了。

[cpp] #include"stdio.h"  
#include"string.h"  
int main() 
{ 
    int T; 
    int n; 
    int i,j,k,l,t; 
    int len,ans; 
    int a[200001]; 
    char s[200001]; 
    scanf("%d",&T); 
    while(T--) 
    { 
        scanf("%d",&n); 
        getchar(); 
        gets(s); 
        len=strlen(s); 
        for(i=0;i<len;i++) 
            a[i]=i; 
        j=len; 
        ans=0; 
        l=0; 
        t=1;//這裡的ｔ初始化跟ans不同就ok  
        while(ans!=t) 
        { 
            t=ans; 
            k=0; 
            for(i=0;i<j&&l<len;i++) 
            { 
                if(s[a[i]]==s[l]&&a[i]<len) 
                { 
                    a[k++]=a[i]+1; 
                    ans++; 
                } 
            } 
            j=k; 
            l++; 
        } 
        printf("%d\n",ans%10007); 
    } 
    return 0; 
} 
                     

#include"stdio.h"
#include"string.h"
int main()
{
 int T;
 int n;
 int i,j,k,l,t;
 int len,ans;
 int a[200001];
 char s[200001];
 scanf("%d",&T);
 while(T--)
 {
  scanf("%d",&n);
  getchar();
  gets(s);
  len=strlen(s);
  for(i=0;i<len;i++)
   a[i]=i;
  j=len;
  ans=0;
  l=0;
  t=1;//這裡的ｔ初始化跟ans不同就ok
  while(ans!=t)
  {
   t=ans;
   k=0;
   for(i=0;i<j&&l<len;i++)
   {
    if(s[a[i]]==s[l]&&a[i]<len)
    {
     a[k++]=a[i]+1;
     ans++;
    }
   }
   j=k;
   l++;
  }
  printf("%d\n",ans%10007);
 }
 return 0;
}