Cod sursa(job #1119722)

Utilizator lilian_ciobanuLilian Ciobanu lilian_ciobanu Data 24 februarie 2014 19:44:15
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include<fstream>
#include<algorithm>
#include<string>
#include<vector>

using namespace std;

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

string s,s1;
vector<int> v(4000009);

int main(){
    getline(f,s);
    getline(f,s1);
    int e=s.length();

    s+='#'+s1;
    int i,n=s.length(),r=0,l=0,k=0;

    for(i=1; i<n; ++i){
        if(i<=r)
            v[i]=min(v[i-l], r-i+1);

        while(i+v[i]<n && s[v[i]]==s[i+v[i]])
            ++v[i];

        if(i + v[i]-1 >r){
            l=i; r=i+v[i]-1;
        }
        if(v[i]==e)
                k++;
    }

    g<<k<<'\n';
    int t=0;
    for(i=e+1; t<=1000 && i<n; ++i)
        if(v[i]==e){
            g<<i-e-1<<' ';
            ++t;
        }

return 0;
}