Cod sursa(job #2001448)

Utilizator roitainNiculae Cristian roitain Data 16 iulie 2017 17:54:36
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include<cstdio>
#include<iostream>
#include<string>
#include<vector>

using namespace std;

void makeTable(string s, vector<int> &table){
    int counter = 0;
    int N = s.size();
    int j = 0;

    for(int i = 1; i<N; ++i){
        while(j>0 && s[j]!=s[i])
            j = table[j-1];

        if(s[j] == s[i])
            ++j;

        table[i] = j;
    }

}

vector<int> KMP(string small, string big, vector<int> table){
    vector<int> result;

    int Ns = small.size();
    int Nb = big.size();

    int j = 0;

    for(int i = 0; i < Nb; ++i){
        if(big[i] == small[j])
            ++j;
        else if(j>0)
            j = table[j-1];
        if(j<0) j = 0;
        if(j == Ns){
            j = table[j-1];
            result.push_back(i - Ns + 1);
        }
    }

    return result;
}

int main(){
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);

    string s1,s2;

    //reading
    cin>>s1;
    cin>>s2;

    vector<int> table(s1.size());

    makeTable(s1,table);
    vector<int> result = KMP(s1,s2,table);

    if(result.size()>1000){
        cout<<1000<<"\n";
        for(int i = 0; i < 1000; ++i)
            cout<<result[i]<<" ";
    }else{
        int Nres = result.size();
        cout<<Nres<<endl;
        for(int i = 0; i < Nres; ++i)
            cout<<result[i]<<" ";
    }
    return 0;

}