Cod sursa(job #1724787)

Utilizator RaduHHarhoi Radu RaduH Data 4 iulie 2016 11:24:29
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <cstring>
#define N 2000010
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char A[N],B[N];
int n,m,pi[N],i,q,nr,poz[1010];
void pref(){
    int i,q=0;
    pi[0]=0;
    for(i=2;i<=m;i++)
    {
        while(q && A[q]!=A[i-1])
            q=pi[q];
        if(A[q]==A[i-1])
            q++;
        pi[i]=q;
    }
}
int main(){
    fin.get(A,N); fin.get();
    fin.get(B,N); fin.get();
    m=strlen(A);
    n=strlen(B);
    pref();
    for(i=1;i<=n;i++)
    {
        while(q && A[q]!=B[i-1])
            q=pi[q];
        if(A[q]==B[i-1])
            q++;
        if(q==m)
        {
            q=pi[m];
            nr++;
            if(nr<=1000)
                poz[nr]=i-m;
        }
    }
    fout<<nr<<'\n';
    for(i=1;i<=nr && i<=1000;i++)
        fout<<poz[i]<<" ";
    fin.close();
    fout.close();
    return 0;
}