Cod sursa(job #923879)

Utilizator BeilandArnoldArnold Beiland BeilandArnold Data 23 martie 2013 22:17:02
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>
#include <vector>
#include <string>
using namespace std;

void getKMPTable(vector<int> &T, const string &A){
    T[0]=-1; T[1]=0;
    unsigned pos=2, currl=0;
    while(pos<A.size()){
        if(A[pos-1]==A[currl]){ currl++; T[pos]=currl; pos++; }
        else if(currl>0) currl=T[currl];
        else{ T[pos]=0; pos++; }
    }
}

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

    string A,B; fin>>A>>B;
    unsigned N=0;
    vector<int> out(1000);
    vector<int> table(A.size());
    getKMPTable(table,A);

    unsigned m=0,i=0;
    while(m+i<B.size()){
        if(B[m+i]==A[i]){
            if(i==A.size()-1){
                if(N<1000) out[N]=m; ++N;
                m+=i-table[i]; i=table[i];
            }
            else ++i;
        }
        else{
            m+=i-table[i];
            if(table[i]<0) i=0;
            else i=table[i];
        }
    }

    fout<<N<<'\n';
    if(N>1000) N=1000;
    for(unsigned i=0;i<N;++i) fout<<out[i]<<' ';
    fout<<'\n';
}