Cod sursa(job #2829660)

Utilizator Mihai_EduardMihai Eduard Mihai_Eduard Data 8 ianuarie 2022 20:30:22
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMAX=2000005;

int N, M, total;
string A, B;
int lps[NMAX];
vector<int> sol;

/// lps[i]=prefixul maxim al subsecventei [0,...,i] care
/// este de asemenea si sufix al aceleasi subsecvente
void computeLPS()
{
    /// lungimea anteriorului prefix maxim care e si sufix
    int len=0;
    lps[0]=0;
    int i=1;
    while(i<N){
        if(A[i]==A[len]){
            lps[i]=len+1;
            len++;
            i++;
        }
        else{
            if(len!=0)
                len=lps[len-1];
            else{
                lps[i]=0;
                i++;
            }
        }
    }
}

void KMP()
{
    computeLPS();
    int i=0, j=0;
    if(N>M)
        return;
    while(i<M){
        if(B[i]==A[j]){
            i++;
            j++;
        }
        else{
            if(j!=0)
                j=lps[j-1];
            else
                i++;
        }
        if(j==N){
            total++;
            if(total<=1000)
                sol.push_back(i-j);
            j=lps[j-1];
        }
    }
}

/// O(N+M)
int main()
{
    fin>>A>>B;
    N=A.size();
    M=B.size();

    KMP();

    fout<<total<<'\n';
    for(auto x: sol)
        fout<<x<<' ';

    fin.close();
    fout.close();
    return 0;
}