2, C++ (gcc) - rextester

2

#include <bits/stdc++.h>

using namespace std;
typedef long long int ll;
#define mp make_pair
#define pb push_back
#define pii pair<int, int>

string s;

vector<int> z, mask;

void KMP(){
    int n = s.length();
    z.resize(n, 0);
    mask.resize(n, 0);
    
    int i = 0;
    for(int j = 1; j < n;){
        if(s[i] == s[j]){
            z[j++] = ++i;
            continue;
        }
        if(i == 0){
            z[j++] = 0;
            continue;
        }
        i = z[i-1];
    }
    
    /*for(int j = 0; j < n; j++){
        int t = z[j];
        int &m = mask[t];
        while(t != 0){
            t |= (1 << )
        }
    }*/
}

string solve(){
    int n = s.length();
    for(int j = 1; j < n-1; j++){
        if(z[j] == 0) continue;
        int t = z[j];
        while(t != 0){
            if(s[t] != s[j+1]){
                string ans = "";
                for(int i = 0; i <= j; i++)
                    ans += s[i];
                for(int i = t; i < n; i++) ans += s[i];
                return ans;
            }
            t = z[t-1];
        }
    }
    return "Impossible";
}

bool cross_check(string t){
    bool fg = 1;
    int n1 = t.length(), n2 = s.length();
    
    int i = 0, j = 0;
    while(i < n1 && j < n2){
        if(t[i] == s[j]){
            i++;
            j++;
            continue;
        }
        if(j == 0){
            i++;
            continue;
        }
        j = 0;
    }
    if(j == n2) return 1;
    return 0;
}

int main(){
    ios_base :: sync_with_stdio(0);
    cin.tie(0);
    
    int t;
    cin >> t;
    for(int i = 1; i <= t; i++){
        cin >> s;
        KMP();
        
        string ans = solve();
        if(ans != "Impossible"){
            bool fg = cross_check(ans);
            assert(fg == false);
        }
        cout << "Case #" << i << ": " << ans << endl;
    }
    return 0;
}


run \| edit \| history \| help	0