Cod sursa(job #857201)

Utilizator alexalghisiAlghisi Alessandro Paolo alexalghisi Data 17 ianuarie 2013 16:20:16
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <iostream>
#include <fstream>
#include <string>
#define un unsigned
using namespace std;

string x,y;
int z[2000005],v[2000005];

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

    getline(f,x);
    getline(f,y);
    y=x+'#'+y;
    int p=0,r=0,ii=0,jj=1,l=0;
    while(y[ii]==y[jj]) ++p,++ii,++jj;
    z[1]=p;
    r=p;
    for(int i=2;i<y.size();++i)
    {
        if(r<i)
        {
            l=r=i;
            while(r<y.size () && y[r-l]==y[r])
                ++r;
            z[i]=r-l;
            --r;
        }
        else
        {
            int k=i-l;
            if(z[k]<r-i+1 ) z[i]=z[k];
            else
            {
                l=i;
                while(r<y.size() && y[r]==y[r-l]) ++r;
                z[i]=r-l;
                --r;
            }
        }
        if(z[i]==x.size())
        {
            v[++v[0]]=i-x.size()-1;
        }
    }
    g<<v[0]<<"\n";
    for(int i=1;i<=min(1000,v[0]);++i)
        g<<v[i]<<" ";
    return 0;
}