Cod sursa(job #2174187)

Utilizator mariakKapros Maria mariak Data 16 martie 2018 11:08:12
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <bits/stdc++.h>
FILE *fin  = freopen("strmatch.in", "r", stdin);
FILE *fout = freopen("strmatch.out", "w", stdout);

using namespace std;
const int Nmax = 2e6+3;
int n, m;
char patt[Nmax], txt[Nmax];
int lsp[Nmax];
int nrap;
vector <int> sol;

void Kmp(){
    int i = 0, j = 0;
    while(i < n){
        if(patt[j] == txt[i])
            j++, i++;
        if(j == m){
            ++ nrap;
            if(sol.size() < 1000)
                sol.push_back(i-j);
            j = lsp[j-1];
        }
        else if(i < n && patt[j] != txt[i]){
            if(j) j = lsp[j-1];
            else ++ i;
        }
    }
}

void Compute_Lsp(){
    lsp[0] = 0;
    int i = 1, len = 0;

    while(i < m){
        if(patt[i] == patt[len]){
            len++;
            lsp[i++] = len;
        }else{
            if(len != 0) len = lsp[len-1];
            else lsp[i++] = 0;
        }
    }
}

void Write(){
    printf("%d\n", nrap);
    for(int i : sol)
        printf("%d ", i);
}

int main(){
    gets(patt), m = strlen(patt);
    gets(txt),  n = strlen(txt);

    Compute_Lsp();
    Kmp();
    Write();
    return 0;
}