Cod sursa(job #1552538)

Utilizator transparentulAlexandra Alexiu transparentul Data 18 decembrie 2015 11:15:04
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <iostream>
#include<fstream>
#include<cstring>

using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");

int i,k,phi[2000010],n,m,v[2000010],nr;
char a[2000010],b[2000010];

void phi1()
{
    int i,k;
    phi[1]=0;
    for (i=2; i<=n; i++)
    {
        k=phi[i-1];
        while (a[i]!=a[k+1] && k>0)
            k=phi[k];
        if (a[i]==a[k+1]) phi[i]=k+1;
        else phi[i]=0;
    }
}
int main()
{
    f.getline(a,2000100);
    f.getline(b,2000100);
    for (i=strlen(a); i>0; i--)
        a[i]=a[i-1];
    for (i=strlen(b); i>0; i--)
        b[i]=b[i-1];
    n=strlen(a)-1;
    m=strlen(b)-1;
a[n+1]=' ';
    a[0]=NULL;
    b[0]=NULL;
    phi1();
    for (i=1; i<=m; i++)
    {
        k=v[i-1];
        while (k>0 && b[i]!=a[k+1])
            k=phi[k];
        if (b[i]==a[k+1])
            v[i]=k+1;
        else v[i]=0;
    }
    for (i=1; i<=m; i++)
        if (v[i]==n) nr++;
    g<<nr<<'\n';
    if (nr>1000)
        nr=1000;
    i=1;
    while (nr>0 && i<=m)
    {
        if (v[i]==n) g<<i-n<<' ';
        i++;
    }

    f.close();
    g.close();
}