Cod sursa(job #2335194)

Utilizator AlexandruPaulSirbu Alex AlexandruPaul Data 3 februarie 2019 18:39:11
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>
#include <fstream>
using namespace std;
const int Maxx=2e6+1;
const int XXX=1e3+1;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n,m;
int ans[XXX];
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 && sol<=1000) {
            ans[++sol]=i-n;
        }
    }
    fout<<sol<<"\n";
    for (int i=1;i<=sol;++i){
        fout<<ans[i]<<" ";
    }
    return 0;
}