Cod sursa(job #1203865)

Utilizator pentrusandaPentru Sanda pentrusanda Data 1 iulie 2014 14:27:54
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream>
#include <cstring>

using namespace std;

char a[4000005],b[2000005];
int n,m,z[4000005];

int main()
{
    ifstream in ("strmatch.in");
    ofstream out ("strmatch.out");

    in>>a;
    in>>b;

    n=strlen(a);
    m=strlen(b);

    a[n]='#'; int j=0;
    for (int i=n+1;i<=n+m;++i) a[i]=b[j],++j;
    m=n+m+1; a[m]='\0';
    int st=0,dr=0,sol=0;
    for (int i=1;i<m;++i)
    {
        if (i<=dr)
        {
            z[i]=z[i-st];
            if (z[i]>dr-i+1) z[i]=dr-i+1;
        }
        while (i+z[i]<m && a[i+z[i]]==a[z[i]]) ++z[i];
        if (dr<i+z[i]-1) dr=i+z[i]-1,st=i;
        if (z[i]==n) ++sol;
    }

    out<<sol<<"\n";

    for (int i=n+1;i<m;++i) if (z[i]==n) out<<i-n-1<<" ";

    in.close();
    out.close();
    return 0;
}