Cod sursa(job #2335196)

Utilizator AlexandruPaulSirbu Alex AlexandruPaul Data 3 februarie 2019 18:42:07
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <iostream>
#include <fstream>
using namespace std;
const int Maxx=2e6+1;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n,m;
int ans[Maxx];
int pi[Maxx];
string A,B;
void prefix(){
    int i,q=0;
    pi[1]=0;
    for (i=2;i<=n;++i){
        while (q && A[q+1]!=A[i]){
            q=pi[q];
        }
        if (A[q+1]==A[i]){
            ++q;
        }
        pi[i]=q;
    }
}
int main() {
    fin>>A>>B;
    n=A.size();
    m=B.size();
    A.insert(0," ");
    B.insert(0," ");
    prefix();
    int q=0;
    int sol=0;
    for (int i=1;i<=m;++i){
        while (q && A[q+1]!=B[i]){
            q=pi[q];
        }
        if (A[q+1]==B[i]){
            ++q;
        }
        if (q==n) {
            ans[++sol]=i-n;
        }
    }
    fout<<sol<<"\n";
    for (int i=1;i<=min(sol,1000);++i){
        fout<<ans[i]<<" ";
    }
    return 0;
}