Cod sursa(job #1716434)

Utilizator BeilandArnoldArnold Beiland BeilandArnold Data 12 iunie 2016 19:27:10
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#include <list>
using namespace std;


void build_pref(const string &s, vector<int> &pref){
    pref[0]=0;

    int q=0;    

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


void kmp(const string &pat, const string &s, int &n, list<int> &lst){
    n=0;
    lst.clear();

    vector<int> pref(pat.size());
    build_pref(pat,pref);

    int q=0;

    //cout<<pat<<'\n';
    //for(int i:pref) cout<<i;
    //cout<<'\n';

    for(int i=0;i<s.size();++i){
        while(q!=0 && s[i]!=pat[q]) q=pref[q-1]; 
        if(s[i]==pat[q]){
            ++q;
            if(q==pat.size()){
                ++n;
                if(lst.size()<1000) lst.push_back(i-pat.size()+1);
                q=pref[q-1];
            }
        }
    }
}



int main(){
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");

    string pat,s;
    fin>>pat>>s;
    
    int n;
    list<int> lst;

    kmp(pat,s,n,lst);

    fout<<n<<'\n';
    for(auto i:lst) fout<<i<<' ';
    fout<<'\n';
}