Source Code
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 7;
int n;

struct hashing {
    long long base ; 
    long long mod1;
    vector<long long> pref; 
    vector<long long> base_power; 

    long long normalize(long long x ){
        return ((x%mod1) + mod1) %mod1 ; 
    }

    void init(string &str_,long long mod1_ = 1e9 +7, long long base_ = 313){

        int sz = str_.size() ; 
        pref.resize(sz) ; 
        base_power.resize(sz) ;
        base = base_ ; 
        mod1 = mod1_ ; 
        
        base_power[0] = 1 ; 
        for(int i = 1 ;i <sz ; i++){
            base_power[i] = (1ll*base*base_power[i-1]) %mod1 ; 
        }

        long long cur = 0 ; 
        for(int i = 0 ; i <sz ; i++){
            cur = (cur*base + str_[i])%mod1;
            pref[i] = cur ; 
        } 
    }

    long long get(int l , int r){
        long long ret = pref[r] ; 
        if(l){
            long long power_difference = base_power[r-l+1]; 
            long long prefix_hash =pref[l-1];
            prefix_hash = (prefix_hash*power_difference)%mod1 ; 
            ret = normalize(ret - prefix_hash) ; 
        }   
        return ret ; 
    }
} h1 , h2 ;


int main()
{
       ios_base::sync_with_stdio(0);
       cin.tie(0);
#ifndef ONLINE_JUDGE
#endif
       
       string a , b; cin >> a >> b; 

       n = a.size() ; 
       int m = b.size() ; 

       h1.init(a) ; 
       h2.init(b) ; 
       if( a == b){
              cout << a; 
              return 0 ; 
       }
       for(int i = 0 ;i < m ; ++ i){
              for(int j = 0 ;j < n ;++ j){
                     long long H1 = h2.get(0 , j) * h1.base_power[i + 1] % h1.mod1 + h1.get(0 , i) ; 
                     H1 %= h1.mod1 ; 
                     long long H2 = h2.get(j + 1, m -1 ) * h1.base_power[n - i - 1] % h1.mod1 + h1.get(i + 1, n - 1) ; 
                     H2 %= h2.mod1 ;
                     if(H1 == H2){
                            cout << b.substr(0 , j + 1) << a.substr(0 , i + 1) ; 
                            return 0 ; 
                     }
              }
       }
       string st = b ; 
       for(int i = 0 ;i + 1< n;++ i){
              st += a[i] ; 
              if(st == a.substr(i + 1, n - i)){
                     cout << st ; 
                     return 0; 
              }
       }
       
       st = a ; 
       for(int i = m - 1; i ; -- i){
              st = b[i] + st ; 
              if(b.substr(0 , i) == st){
                     cout << st; 
                     return 0; 
              }
       }
       cout << -1 ; 

       return 0;
}
Copy
Right into Two Mohamed.Sobhy
GNU G++17
0 ms
688 KB
Wrong Answer