Cod sursa(job #1119683)

Utilizator lilian_ciobanuLilian Ciobanu lilian_ciobanu Data 24 februarie 2014 19:30:06
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 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(){
    f>>s>>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';
    for(i=e+1; i<n; ++i)
        if(v[i]==e)
            g<<i-e-1<<' ';


return 0;
}