Cod sursa(job #2118700)

Utilizator LucaSeriSeritan Luca LucaSeri Data 30 ianuarie 2018 21:23:18
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("potriveala.in");
ofstream g("potriveala.out");

const int MAXN = 250010;

bool viz[MAXN];
int pi[MAXN];

int main(){
    string a, b;
    f >> b >> a;

    a = ' ' + a;
    b = ' ' + b;

    pi[1] = 0;
    int q = 0;
    for(int i = 2; i < a.size(); ++i){
        while(q && a[q+1] != a[i]) q = pi[q];
        if(a[q+1] == a[i]) ++ q;
        pi[i] = q;
    }

    q = 0;

    for(int i = 1; i < b.size(); ++i){
        while(q && a[q+1] != b[i]) q = pi[q];
        if(a[q+1] == b[i]) ++ q;
        if(q == a.size()-1){
            q = pi[q];
            viz[i-a.size()+3] ^= 1;
        }
    }

    int best = 0;

    for(int i = 1; i < b.size(); ++i){
        if(viz[i]){
            viz[i] ^= 1;
            int j = i;
            int k = i;
            while(viz[j + a.size() - 1] && j + a.size() - 1  < b.size()){
                j += a.size() - 1;
                viz[j] ^= 1;
            }

            j += a.size() - 2;
            int jj = j;
            while(b[k-2] == a[a.size() - (i-k+1)] && k > 2 && (i- k + 1) < a.size()) --k;
            while(b[j+1] == a[j+1-jj + 1] && j < b.size() - 1) ++j;
            j = min(j, (int)(b.size() - 1));
            best = max(best, j - k + 1);
        }
    }

    g << best;
    return 0;
}