Cod sursa(job #2883967)

Utilizator valentinchipuc123Valentin Chipuc valentinchipuc123 Data 2 aprilie 2022 01:27:59
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

int N,M,pi[2000005];
string A,B;

void make_prefix(void)
{
	int i, q = 0;

	for (i = 2, pi[1] = 0; i <= M; ++i)
	{
		while (q && A[q+1] != A[i])
			q = pi[q];
		if (A[q+1] == A[i])
			++q;
		pi[i] = q;
	}
}

int main()
{
    f>>A>>B;
    M=A.size();
    N=B.size();
    A=" "+A;
    B=" "+B;

    make_prefix();

    int poz=0;
    vector<int>elem;

    for(int i=1; i<=N; i++)
    {
        while( poz&&A[poz+1]!=B[i] ) poz=pi[poz];
        if(A[poz+1]==B[i]) poz++;

        if(poz==M)
        {
            poz=pi[poz];
            if(elem.size()<1000) elem.push_back(i-M);
        }
    }

    g<<elem.size()<<'\n';
    for(int i=0; i<elem.size(); i++) g<<elem[i]<<' ';

    return 0;
}