Cod sursa(job #857217)

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

string x,y;
int z[4000005],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;
    for(int i=1;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;
}