Cod sursa(job #1218158)

Utilizator rangerChihai Mihai ranger Data 9 august 2014 18:32:24
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include<fstream>
#include<vector>
#include<string>
using namespace std;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

string s,p,t;
int n,m,z[4000000],k=0,sol[2000000];
int main()
{
    getline(cin,p);
    getline(cin,t);
    s=p+'*'+t;
    int n=s.size();
    for (int i=1,l=0,r=0;i<n;i++)
    {
        if (i<=r)
            z[i]=min(z[i-l],r-i+1);
        while (i+z[i]<n && s[z[i]]==s[z[i]+i]) ++z[i];
        if (i+z[i]-1>r)
            l=i, r=i+z[i]-1;
    }
    for (int i=0;i<t.size();i++)
         if (z[i+p.size()+1]==p.size())
            sol[++k]=i;
    cout<<k<<"\n";
    for (int i=1;i<=k;i++) cout<<sol[i]<<" ";
    return 0;
}