Cod sursa(job #1719737)

Utilizator stefan.botezStefan Botez stefan.botez Data 20 iunie 2016 10:16:17
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int main()
{
    string p,s;
    f>>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];
        }
    }
    g<<nr<<'\n';
    for(int i=0;i<cnt;i++) g<<matches[i]<<' ';
}