Cod sursa(job #1551553)

Utilizator andreea_zahariaAndreea Zaharia andreea_zaharia Data 16 decembrie 2015 00:04:58
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int NMAX = 2000005;

char A[NMAX], B[NMAX];
int pi[NMAX];
int sol[NMAX];
int lenA, lenB;

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

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

    lenA = strlen(A + 1);
    lenB = strlen(B + 1);

    int k = 0;
    pi[1] = 0;

    for (int i = 2; i <= lenA; 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 <= lenB; i++)
    {
        while (k > 0 && B[i] != A[k + 1]) {
            k = pi[k];
        }

        if (B[i] == A[k + 1]) {
            k++;
        }

        if (k == lenA) {
            sol[++sol[0]] = i - lenA;
            k = pi[k];
        }
    }

    printf ("%d\n", sol[0]);

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

    printf ("\n");

    return 0;
}