Cod sursa(job #1821159)

Utilizator BeilandArnoldArnold Beiland BeilandArnold Data 2 decembrie 2016 18:56:56
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <fstream>
#include <string>
#include <vector>
using namespace std;

int main(){
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    string p,s;
    fin>>p>>s;

    int nr=0,cnt=0;
    vector<int> matches(1000);

    int n=s.size(),m=p.size();

    vector<int> pref(m);

    pref[0]=0;
    int q=0;
    for(int i=1;i<m;++i){
        while(q!=0 && p[i]!=p[q]) q=pref[q-1];
        if(p[i]==p[q]) ++q;
        pref[i]=q;
    }

    q=0;
    for(int i=0;i<n;++i){
        while(q!=0 && s[i]!=p[q]) q=pref[q-1];
        if(s[i]==p[q]) ++q;
        if(q==m){
            ++nr;
            if(cnt<1000) matches[cnt++]=i-m+1;
            q=pref[q-1];
        }
    }



    fout<<nr<<'\n';
    for(int i=0;i<cnt;++i) fout<<matches[i]<<' ';
    fout<<'\n';

}