Cod sursa(job #2734680)

Utilizator Mihai7218Bratu Mihai-Alexandru Mihai7218 Data 1 aprilie 2021 11:26:53
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char A[2000008], B[2000008];
int pi[2000008], i, cnt, pcnt, M, N;
queue<int> Q;
void kmp()
{
    int k = 0;
    pi[1] = 0;
    for (i = 2; i <= M; i++)
    {
        while(k>0 && A[k+1] != A[i])
            k = pi[k];
        if (A[k+1] == A[i])
            k++;
        pi[i] = k;
    }
}
int main()
{
    fin >> A >> B;
	/*for (; (A[M] >= 'A' && A[M] <= 'Z') || (A[M] >= 'a' && A[M] <= 'z')
			|| (A[M] >= '0' && A[M] <= '9'); ++M);
	for (; (B[N] >= 'A' && B[N] <= 'Z') || (B[N] >= 'a' && B[N] <= 'z')
			|| (B[N] >= '0' && B[N] <= '9'); ++N);*/
    M = strlen(A);
    N = strlen(B);
	for (i = M; i; --i) A[i] = A[i-1]; A[0] = ' ';
	for (i = N; i; --i) B[i] = B[i-1]; B[0] = ' ';
    kmp();
    int q = 0;
    for (i = 1; i <= N; i++)
    {
        while (q > 0 && A[q+1]!= B[i])
            q = pi[q];
        if (A[q+1] == B[i])
            q++;
        if (q == M)
        {
            cnt++;
            if (cnt <= 1000)
                Q.push(i-M);
        }
    }
    fout << cnt << "\n";
    while (! Q.empty())
    {
        fout << Q.front() << " ";
        Q.pop();
    }
    return 0;
}