Cod sursa(job #2416252)

Utilizator LittleWhoFeraru Mihail LittleWho Data 27 aprilie 2019 11:31:01
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;
typedef signed long long ll;
typedef unsigned int uint;
typedef unsigned short ushort;
typedef unsigned char uchar;
const int nmax = 2000001;
const int smax = 2001;

char A[nmax];
char B[nmax];
int sol_cnt;
int sol[nmax];
int lsp[nmax];

void kmp_query(char *pattern, char *text) {
    int pattern_len = strlen(pattern);
    int text_len = strlen(text);

    for (int i = 1, k = 0; i < pattern_len; i++) {
        while (k && pattern[k] != pattern[i]) k = lsp[k - 1];
        if (pattern[k] == pattern[i]) k++;
        lsp[i] = k;
    }

    for (int i = 0, k = 0; i < text_len; i++) {
        while (k && pattern[k] != text[i]) k = lsp[k - 1];
        if (pattern[k] == text[i]) ++k;
        if (k == pattern_len) {
            sol[sol_cnt++] = i - k + 1;
        }
    }
}

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

    scanf("%s", A);
    scanf("%s", B);

    kmp_query(A, B);

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

    return 0;
}