Cod sursa(job #2417390)

Utilizator alex2kamebossPuscasu Alexandru alex2kameboss Data 29 aprilie 2019 17:35:05
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>

#define N 2000005

using namespace std;

char a[N], txt[N];
int lp[N];
int lena, lenb;
vector <int> sol;

inline void prefix(){
    int j = 0;
    for(int i = 1; i < lena; ++i){
        if(a[i] == a[j])
            lp[i] = ++j;
        else{
            --j;
            while(j>=0){
                j=lp[j];
                if(a[i] == a[j]){
                    lp[i] = ++j;
                    break;
                }else
                    --j;
            }
            if(j<0)
                lp[i] = j = 0;
        }
    }
}

inline void kmp(){
    int i=0, j=0;
    while(i<lenb){
        if(a[j] == txt[i])
            ++i, ++j;
        if(j==lena){
            sol.push_back(i-lena);
            j=lp[j-1];
        }
        else if(i<lenb && a[j]!=txt[i]){
            if(j!=0)
                j = lp[j-1];
            else
                ++i;
        }
    }
}

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

    fgets(a,N,stdin);
    fgets(txt,N,stdin);
    lena = strlen(a) - 1;
    lenb = strlen(txt) - 1;

    prefix();
    kmp();

    cout<<sol.size()<<"\n";
    int len = sol.size();
    len = min(len, 1000);
    for(int i = 0; i < len; ++i)
        cout<<sol[i]<<" ";

    return 0;
}