Cod sursa(job #1719729)

Utilizator stefan.botezStefan Botez stefan.botez Data 20 iunie 2016 10:07:52
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
#include <cstring>

using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[2000005],b[2000005];
int p[2000005],pos[1010],n;
int main()
{
    f>>a;
    f>>b;
    int i,q=0;p[1]=0;
    for (i=strlen(a);i;i--)a[i]=a[i-1];a[0]=' ';
    for (i=strlen(b);i;i--)b[i]=b[i-1];b[0]=' ';
    for (i=2;i<=strlen(a);i++)
    {
        while(q&&a[q+1]!=a[i])
            q=p[q];
        if(a[q+1]==a[i])
            q++;
        p[i]=q;
    }
    q=0;
    for(i=1;i<=strlen(b)-1;i++)
    {
        while(q&&a[q+1]!=b[i])
            q=p[q];
        if(a[q+1]==b[i])
            q++;
        if(q==strlen(a)-1)
        {
            q=p[strlen(a)-1];
            n++;
            if(n<=1000)
                pos[n]=i-strlen(a)+1;
        }
    }
    g<<n<<endl;
    for(i=1;i<=min(n,1000);i++)
        g<<pos[i]<<" ";
    return 0;
}