校赛——1096Is The Same?（KMP或字符串的最小、大表示法）-白红宇

校赛——1096Is The Same?（KMP或字符串的最小、大表示法）

阅读量：4663 次

发布时间：2019-06-09

本文共 1744 字，大约阅读时间需要 5 分钟。

1096: Is The Same?

Time Limit: 1 Sec Memory Limit: 64 MB

Submit: 26 Solved: 8

[][][]

Description

给出2个字符串S和T,如果可以通过循环移位使得S和T相等,则我们称S和T是同构字符串, 例如S=“abcd”, T=“bcda”,则S和T是同构字符串;而S=“abcd”和T=“bcad”则不是同构字符串。

循环移位是指:在⼀个长度为n的字符串S中,取⼀个任意下标i,把字符串分为两段,分别为 S1S2...Si 和Si+1Si+2...Sn,然后把字符串变为Si+1Si+2...SnS1S2...Si,例如S=“qwerty”,取i=3, 则变为”rtyqwe”(注意,一个字符串本⾝身也算是它的同构字符串)。

Input

第⼀行包含一个整数T(1 <= T <= 20),代表测试组数。

对于每组数据,包含2个字符串,字符串长度都小于等于105且非空,输入保证字符串只包含小写字⺟。

Output

对于每组数据,如果这两个字符串是同构字符串,则输出Yes,否则输出No。

Sample Input

2abcdbcdaabcdbcad

Sample Output

YesNo

比赛的时候用的是据说效率差不多的strstr过的，毕竟题目只是要求输出是否匹配而不是查找出现位置。KMP比较长打起来费时间而且清空数组又要打一堆

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 using namespace std;typedef long long LL;#define INF 0x3f3f3f3f#define MM(a) memset(a,0,sizeof(a))const int N=100010;char a[N],b[N],aa[2*N],bb[2*N];int nexta[N],nextb[N];inline void getnext(int ne[],char s[]){ int j=0,k=ne[0]=-1; int len=strlen(s); while (j

最小表示法代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 using namespace std;typedef long long LL;#define INF 0x3f3f3f3finline string minP(string s){ int i=0,j=1,k=0,l=s.size(); while (i
                  
                   
                    
                     0) j+=k+1; else i+=k+1; k=0; if(i==j) j++; } } s=s+s; return s.substr(min(i,j),l);}int main(void){ int tcase; string a,b; cin>>tcase; while (tcase--) { cin>>a>>b; a=minP(a); b=minP(b); if(a==b) cout<<"Yes"<

转载于:https://www.cnblogs.com/Blackops/p/5475411.html

你可能感兴趣的文章