算法训练字串统计

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

//next是子串

算法训练字串统计

时间限制：1.0s 内存限制：512.0MB

问题描述

　　给定一个长度为n的字符串S，还有一个数字L，统计长度大于等于L的出现次数最多的子串（不同的出现可以相交），如果有多个，输出最长的，如果仍然有多个，输出第一次出现最早的。

输入格式

　　第一行一个数字L。
　　第二行是字符串S。
　　L大于0，且不超过S的长度。

输出格式

　　一行，题目要求的字符串。

　　输入样例1：
　　4
　　bbaabbaaaaa

　　输出样例1：
　　bbaa

　　输入样例2：
　　2
　　bbaabbaaaaa

　　输出样例2：
　　aa

数据规模和约定

　　n<=60
　　S中所有字符都是小写英文字母。

　　提示
　　枚举所有可能的子串，统计出现次数，找出符合条件的那个

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char s[1005];
int sl,next[1005];
void get_next(char *p,int pl)
{
    int k=-1,j=0;
    next[0]=-1;
    while(j<pl)
    {
        if(k==-1||p[j]==p[k])
        {
            j++;
            k++;
            next[j]=k;
        }
        else
          k=next[k];
    }
}
int kmp(char *p,int pl)
{
    int sum=0;
    int i=0,j=0;

    while(j<pl&&i<sl)
    {
        if(j==-1||s[i]==p[j])
        {
            i++;
            j++;

        }
        else
           j=next[j];
         if(j==pl)
         {
             sum++;
             //printf("sum2=%d\n",sum);
             j=next[j];

         }
    }

   return sum;
}
int main()
{
    int n,i,sum,f,r,j,k;
    int max=0;

    scanf("%d",&n);
    scanf("%s",s);
     sl=strlen(s);
      char  p[1005];
    for(i=n;i<=sl;i++)
     {
         for(j=0;j<=sl-i;j++)
         {
             sum=0;
              int q=0;
             int x=0;
             for(k=j;x<i;k++)
             {
                p[q++]=s[k];
                   x++;

             }
             p[q]=‘\0‘;
             memset(next,0,sizeof(next));
              get_next(p,q);
               sum=kmp(p,q);
                if(sum>max)
                  {
                      max=sum;
                      f=j;
                      r=i;
                  }
                  if(sum==max)
                  {
                      if(i>r)
                      {
                          f=j;
                          r=i;
                      }
                  }
                }
       }
    int y=0;
     for(i=f;y<r;i++)
     {
         y++;
        printf("%c",s[i]);
     }

     printf("\n");
     return 0;

}