Cod sursa(job #1193011)

Utilizator gbibBacotiu Gabi gbib Data 30 mai 2014 17:15:35
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#include <cstring>
#define nmax 2000005
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char n[nmax],m[nmax];
int ln,lm,k,i,q,cont;
int pr[nmax],potr[nmax];
int main()
{
    in>> (n + 1);
    in>> (m + 1);
    ln=strlen(n+1);
    lm=strlen(m+1);
    k=0;
    cont=0;
    pr[1]=0;
    for(i=2;i<=ln;i++)
    {
        while(k&&n[k+1]!=n[i])
            k=pr[k];
        if(n[k+1]==n[i])
            k++;
        pr[i]=k;
    }
    q=0;
    for(i=1;i<=lm;i++)
    {
        while(q&&n[q+1]!=m[i])
        q=pr[q];
        if(n[q+1]==m[i])
            q++;
        if(q==ln)
        {

                potr[++cont]=i-ln;
             q = pr[q];
        }
    }
    if (cont> 1000) cont = 1000;
out<<cont<<'\n';
for(i=1;i<=cont;i++)
    out<<potr[i]<<" ";
out<<'\n';
    return 0;
}