Cod sursa(job #2242449)

Utilizator GeorgianBaditaBadita Marin-Georgian GeorgianBadita Data 18 septembrie 2018 18:17:10
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <cstring>
#include <cstdio>
#define MIN(A,B) (A <= B ? A : B)
#define NMAX 2000005
using namespace std;




int lsp[NMAX], matches[NMAX], app;
char text[NMAX], pattern[NMAX];

void read_data(){
    FILE* f = freopen("strmatch.in", "r", stdin);
    gets(pattern + 1);
    gets(text + 1);
    text[0] = '&';
    pattern[0] = '&';
}

void build_lsp(){
    int k = 0;
    lsp[1] = 0;
    int m = strlen(pattern) - 1;
    for(int i = 2; i<= m; i++){
        while(k > 0 && pattern[i] != pattern[k + 1]){
            k = pattern[k];
        }
        if(pattern[k + 1] == pattern[i]){
            k ++;
        }
        lsp[i] = k;
    }
}

void solve_kmp(){
    build_lsp();
    int n = strlen(text) - 1;
    int m = strlen(pattern) - 1;
    int q = 0;
    for(int i = 1; i<=n; i++){
        while(q != 0 && pattern[q + 1] != text[i]){
            q = lsp[q];
        }
        if(pattern[q + 1] == text[i]){
            q ++;
        }
        if(q == m){
            app ++;
            if(app <= 1000){
                matches[app] = i - m;
            }
            q = lsp[q];
        }
    }
}

int main(){
    FILE* g = freopen("strmatch.out", "w", stdout);
    read_data();
    solve_kmp();
    printf("%d\n", app);
    for(int i =1; i<=MIN(1000, app); i++){
        printf("%d ", matches[i]);
    }
    return 0;
}