Advertisement
MAGCARI

Secret Code

Jan 28th, 2023 (edited)
1,197
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.89 KB | None | 0 0
  1. /*
  2.     Task    : _example
  3.     Author  : Phumipat C. [MAGCARI]
  4.     Language: C++
  5.     Created : 30 January 2023 [21:31]
  6. */
  7. #include<bits/stdc++.h>
  8. using namespace std;
  9. char a[1000010],b[1000010];
  10. int prep[1000010];
  11. char ans[1000010];
  12. int jump[1000010];
  13. int main(){
  14.     cin.tie(0)->sync_with_stdio(0);
  15.     cin.exceptions(cin.failbit);
  16.     int q;
  17.     cin >> q;
  18.     while(q--){
  19.         cin >> a+1 >> b+1;
  20.         int lena = strlen(a+1),lenb = strlen(b+1);
  21.         int j = 0;
  22.         for(int i=2;i<=lenb;i++){
  23.             while(j>0 && b[j+1]!=b[i])  j = prep[j];
  24.             if(b[j+1]==b[i])    j++;
  25.             prep[i] = j;
  26.         }
  27.         j=0;
  28.         int idx=0;
  29.         for(int i=1;i<=lena;i++){
  30.             while(j>0 && b[j+1]!=a[i])  j = prep[j];
  31.             if(b[j+1]==a[i])    j++;
  32.             ans[++idx] = a[i];
  33.             jump[idx] = j;
  34.             if(j == lenb){
  35.                 idx-=lenb;
  36.                 j = jump[idx];
  37.             }
  38.         }
  39.         ans[idx+1] = '\0';
  40.         if(idx == 0)    cout << "No COI Secret Code\n";
  41.         else            cout << ans+1 << "\n";
  42.     }
  43.     return 0;
  44. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement