Educational Codeforces Round 102

B. String LCM

#include<bits/stdc++.h>
using namespace std;
int Next[10005];
void getNext(string T, int tlen)
{
    int j, k;
    j = 0; k = -1; Next[0] = -1;
    while(j < tlen)
        if(k == -1 || T[j] == T[k])
            Next[++j] = ++k;
        else
            k = Next[k];
}
int main(){
  int q;
  cin>>q;
  while(q--){
      string s,t;
      cin>>s>>t;
      s+=s;
      t+=t;
      int lens=s.size();
      int lent=t.size();
      string subs="",subt="";
      memset(Next,0,sizeof(Next));
      getNext(s,lens);
      int lensubs=lens-Next[lens];
      for(int i=0;i<lensubs;i++) subs+=s[i];
      memset(Next,0,sizeof(Next));
      getNext(t,lent);
      int lensubt=lent-Next[lent];
      for(int i=0;i<lensubt;i++) subt+=t[i];
      if(subs==subt){
          string res="";
          int x = lens/lensubs;
          int y = lent/lensubt;
          x/=2;
          y/=2;
          int num = x*y/__gcd(x,y);
          for(int i=0;i<num;i++){
              res+=subs;
          }
          cout<<res<<endl;
      }else{
          cout<<-1<<endl;
      }
  }
}

方法二
注意
采用getNext()这个函数，要从下标为1开始
要求字符串的循环子串要先乘2

#include<bits/stdc++.h>
using namespace std;
int Next[30];
void getNext(string s,int n){
    Next[1]=0;
    for(int i=2,j=0;i<=n;i++){
        while(j>0&&s[i]!=s[j+1]) j=Next[j];
        if(s[i]==s[j+1]) j++;
        Next[i]=j;
    }
    return;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        string a,b;
        cin>>a>>b;
        a+=a;
        b+=b;
        int alen = a.size();
        a+=a[alen-1];
        for(int i=alen-1;i>0;i--){
            a[i]=a[i-1];
        }
        getNext(a,alen+1);
        int t = alen - Next[alen];
        string x="";
        if(alen%t==0){
            for(int i=1;i<=t;i++){
                x+=a[i];
            }
            int blen = b.size();
            b+=b[blen-1];
            for(int i=blen-1;i>0;i--){
                b[i]=b[i-1];
            }
            
            memset(Next,0,sizeof(Next));
            getNext(b,blen);
            int t1 = blen - Next[blen];
            string y="";
            if(blen%t1==0){
                for(int i=1;i<=t1;i++){
                    y+=b[i];
                }
                if(x==y){
                    int m=alen/t;
                    int n=blen/t1;
                    m/=2,n/=2;
                    int times=m*n/__gcd(m,n);
                    for(int i=0;i<times;i++){
                        cout<<x;
                    }
                    cout<<endl;
                }else{
                    cout<<-1<<endl;
                }
            }else{
                cout<<-1<<endl; 
            }
        }else{
            cout<<-1<<endl;
        }
    }
    return 0;
}