Cod sursa(job #2066711)

Utilizator EuAlexOtaku Hikikomori EuAlex Data 15 noiembrie 2017 12:50:11
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <cstdio>
#include <cstring>
#include <vector>
#include <cassert>

using namespace std;

char pat[2000005], txt[2000005];
int dp[2000005], n, m;
vector <int> sol;

void buildPre() {
    int len = 0, i = 1;
    dp[0] = 0;

    while(i < n) {
        if(pat[len] == pat[i]) {
            ++ len;
            dp[i] = len;
            ++ i;
        } else {
            if(len > 0) {
                len = dp[len - 1];
            } else {
                dp[i] = 0;
                ++ i;
            }
        }
    }
}

void searchKmp() {
    int i = 0, j = 0;

    while(j < m) {
        if(pat[i] == txt[j]) {
            ++ i;
            ++ j;
        }

        if(i == n) {
            sol.push_back(j - i);
            i = dp[i - 1];

            if(sol.size() == 1000) {
                return ;
            }
        } else if(j < m && pat[i] != txt[j]){
            if(i > 0) {
                i = dp[i - 1];
            } else {
                ++ j;
            }
        }
    }
}

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

    gets(pat);
    gets(txt);

    n = strlen(pat);
    m = strlen(txt);

    buildPre();
    searchKmp();

    printf("%d\n", sol.size());
    for(int i = 0; i < sol.size(); ++ i) {
        printf("%d ", sol[i]);
    }

    return 0;
}