Cod sursa(job #1386881)

Utilizator rangerChihai Mihai ranger Data 13 martie 2015 14:26:19
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include<fstream>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

string s,t,p;
int n,m;
int z[4000003];
vector<int> sol;

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

    cin>>p>>t;
    s=p+"!"+t;
    n=s.size();
    //cout<<s<<'\n';
    for (int i=1,l=0,r=0;i<n;i++)
    {
        if (i<=r) z[i]=min(r-i+1,z[i-l]);
        while (i+z[i]<n && s[z[i]]==s[i+z[i]])z[i]++;
        r=i+z[i]-1; l=i;
    }
    //for (int i=1;i<n;i++) cout<<z[i]<<' ';
    for (int i=0;i<t.size();i++)
        if (z[i+1+p.size()]==p.size()) sol.push_back(i);
    int k=sol.size();
    cout<<sol.size()<<'\n';
    for (int i=0;i<min(k,1000);i++) cout<<sol[i]<<' ';

    return 0;
}