循环移位(Cycle)

描述

所谓循环移位是指。一个字符串的首字母移到末尾, 其他字符的次序保持不变。比如ABCD经过一次循环移位后变成BCDA

给定两个字符串,判断它们是不是可以通过若干次循环移位得到彼此

 

 

输入

由m行组成,每行包含两个由大写字母’A’~’Z’组成的字符串,中间由空格隔开

 

 

输出

对于每行输入,输出这两个字符串是否可以通过循环移位得到彼此:YES表示是,NO表示否

 

 

输入样例

AACD CDAA

ABCDEFG EFGABCD

ABCD ACBD

ABCDEFEG ABCDEE

 

 

输出样例

YES

YES

NO

NO

 

 

限制

0 ≤ m ≤ 5000

1 ≤ |S1|, |S2| ≤ 10^5

时间:2s,内存:256MB

 

 

 

 

   这题我的想法是,先把第一个字符串s加倍,让两个s一前一后合并为一个新的s;然后算出第二个字符串p的改进KMP的f[]失败函数;然后自己改一下FindKMP,查找s中有没有p,就可以啦~~

 

 

#include
//#include

using namespace std;

template
void Fail(T str,int f[],int n) //书P64失败算法
{
   int j=0,k=-1;
   f[0]=-1;
   while(j    {
       if((k==-1) || (str[j]==str[k]))
       {
           j++;k++;
           f[j]=k;
       }
       else k=f[k];
   }
}

template
void FFail(T str,int f[],int n)  //书P65改进失败函数算法
{
   int j=0,k=-1;f[0]=-1;
   while(j    {
       if((k==-1) || (str[j]==str[k]))
       {
           j++;k++;
           if(str[j]==str[k]) f[j]=f[k];
           else f[j]=k;
       }
       else k=f[k];
   }
}

bool FindKMPX(string s,string p,int f[],int sl,int pl)  //改编为适用于本题的FindKMP算法
{
   int i,j;
   i=0;
   //cout<<"sl="<>t;
       for(j=0;i        {
           if(p[j]==s[i])
           {
               if(j==pl-1) return true;
               else {i++;j++;}
           }
           else if(f[j]!=-1) j=f[j];
               else {i++;j=0;}
       }

   return false;
}

int main()
{
   while(1)
   {
       string s;
       cin>>s;//cout<        s=s+s;int l;l=s.size();
       //cout<        string p;
       cin>>p;
       int ll;ll=p.size();
       int *f;f=new int[ll+1];
       Fail(p,f,ll);//for(int i=0;i        FFail(p,f,ll);
       //for(int i=0;i        //cout<        if(FindKMPX(s,p,f,l,ll)) cout<<"YES"<        else cout<<"NO"<    }

 

   return 0;
}

 

 

 

   但是为什么提交到OJ上全部超时呢?~~~我觉得可能是题目不完整吧~~题目中有个m行,可是在输入里却没有m~~可能是它给的输入格式不对吧~~~~~~当然啦,有没有大神能提出一点优化建议的呢?~谢谢啦~~

 

   后来去OJ的讨论区,发现也有好多人跟我有同样的问题,老师说:可以用 while (scanf(“kj;asjfosafpojago”, &a, &b) != EOF) 判断程序结束~~受到启发,百度之,发现 while(cin>>a>>b) 也就可以了~~于是更改后的新程序提交OJ,跑出来了90分,只有一组错,好奇怪,比它规模大和规模小的组都是正确的答案,为什么就这一组错呢?莫非是边界问题?~~

 

 

#include
//#include
//#include

using namespace std;

template
void Fail(T str,int f[],int n) //书P64失败算法
{
   int j=0,k=-1;
   f[0]=-1;
   while(j    {
       if((k==-1) || (str[j]==str[k]))
       {
           j++;k++;
           f[j]=k;
       }
       else k=f[k];
   }
}

template
void FFail(T str,int f[],int n)  //书P65改进失败函数算法
{
   int j=0,k=-1;f[0]=-1;
   while(j    {
       if((k==-1) || (str[j]==str[k]))
       {
           j++;k++;
           if(str[j]==str[k]) f[j]=f[k];
           else f[j]=k;
       }
       else k=f[k];
   }
}

bool FindKMPX(string s,string p,int f[],int sl,int pl)  //改编为适用于本题的FindKMP算法
{
   int i,j;
   i=0;
   //cout<<"sl="<>t;
   for(j=0;i    {
       if(p[j]==s[i])
       {
           if(j==pl-1) return true;
           else {i++;j++;}
       }
       else if(f[j]!=-1) j=f[j];
           else {i++;j=0;}
   }

   return false;
}

int main()
{
   string s,p;
   while(cin>>s>>p)
   {
       //cout<        s=s+s;int l;l=s.size();
       //cout<        int ll;ll=p.size();
       int *f;f=new int[ll+1];
       Fail(p,f,ll);//for(int i=0;i        FFail(p,f,ll);
       //for(int i=0;i        //cout<        if(FindKMPX(s,p,f,l,ll)) cout<<"YES"<        else cout<<"NO"<    }

 

   return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注