Cod sursa(job #2829648)

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

using namespace std;

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

int N, M;
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)
            sol.push_back(i-j);
    }
}

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

    KMP();

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

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