Cod sursa(job #2466819)

Utilizator educationalLets Go educational Data 2 octombrie 2019 23:11:49
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <bits/stdc++.h>
#define MaxN 2000000
#define MaxS 1000
using namespace std;

char A[MaxN + 2];
char B[MaxN + 2];
int sol[MaxS + 1];
int pi[MaxN + 1];
int N, M;

int main(){

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

    int i, k, res = 0;

    scanf("%s", A);
    scanf("%s", B);
    N = strlen(A);
    M = strlen(B);

    for(i = N; i >= 1; i--) A[i] = A[i-1];
    for(i = M; i >= 1; i--) B[i] = B[i-1];

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

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

        if(k == N)
            if(res < 1000) sol[++res] = i;
            else ++res;
    }

    cout << res << '\n';
    for(i = 1; i <= min(1000, res); i++) cout << sol[i] << ' ';




return 0;
}