Cod sursa(job #1525758)

Utilizator deividFlorentin Dumitru deivid Data 15 noiembrie 2015 15:45:43
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <stdio.h>
#include <cstring>
#include <vector>

#define maxdim 2000005

using namespace std;

int n, m;
char A[maxdim], B[maxdim];
int pi[maxdim];
int sol;
vector<int> sols;

int main() {

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

    scanf("%s\n%s\n", A+1, B+1);
    int n = strlen(A+1);
    int m = strlen(B+1);

    int k = 0;
    for (int i = 2; i <= n; ++i) {
        while (k > 0 && A[i] != A[k+1]) {
            k = pi[k];
        }
        if (A[i] == A[k+1]) {
            ++k;
        }
        pi[i] = k;
    }

    k = 0;
    for (int i = 1; i <= m; ++i) {
        while (k > 0 && B[i] != A[k+1]) {
            k = pi[k];
        }
        if (B[i] == A[k+1]) {
            ++k;
        }
        if (k == n) {
            ++sol;
            if (sol < 1000) {
                sols.push_back(i - n);
            }
        }
    }

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

    return 0;
}