Cod sursa(job #2172080)

Utilizator catalinlupCatalin Lupau catalinlup Data 15 martie 2018 14:58:10
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>
#define INFILE "strmatch.in"
#define OUTFILE "strmatch.out"
using namespace std;
ifstream in(INFILE);
ofstream out(OUTFILE);
vector<int> rasp;
void GeneratePrefixTable(string needle,int p[]){
    int len=0;
    p[0]=0;
    int i=1;
    int N=needle.length();
    while(i<N){
        if(needle[len]==needle[i]){
            len++;
            p[i]=len;
            i++;
        }
        else if(len==0){
            p[i]=0;
            i++;
        }
        else{
            len=p[len-1];
        }
    }
}

void KMP(string haysack,string needle){
    int M=needle.length();
    int p[M];
    GeneratePrefixTable(needle,p);
    int N=haysack.length();
    int i=0,j=0;
    while(i<N){
        if(haysack[i]==needle[j]){
            i++;
            j++;
        }
        if(j==M){
            //cout<<"Pattern found "<<i-j<<"\n";
            rasp.push_back(i-j);
            j=p[j-1];
        }
        else if(i<N&&haysack[i]!=needle[j]){
            if(j>0){
                j=p[j-1];
            }
            else{
                i++;
            }
        }
    }
}

int main(){
    string needle;
    string haysack;
    in>>needle>>haysack;
    KMP(haysack,needle);
    out<<rasp.size()<<"\n";
    for(auto r:rasp){
        out<<r<<" ";
    }
    return 0;
}