Cod sursa(job #2572153)

Utilizator monaaMona Dumbravescu monaa Data 5 martie 2020 11:55:01
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include <bits/stdc++.h>
using namespace std;
const int MAX = 2000010; // TODO: fix
char A[MAX], B[MAX];
int Store[1000], pi[MAX];
int n, m, i, k, nr;

int main()
{
	ifstream f("strmatch.in");
	ofstream g("strmatch.out");
	f >> A >> B;
 	n = strlen(A);
	m = strlen(B);
	pi[1] = 0; k = 0;
	for(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(i = 1; i <= m; i ++)
	{
		while(A[k + 1] != B[i] && k > 0) k = pi[k];
		if(A[k + 1] == B[i]) k ++;
		if(k == n)
		{
			nr ++;
			if(Store[0] < 1000)
				Store[++Store[0]] = i - n;
		}
	}
    g << nr << "\n";
	for(i = 1; i <= Store[0]; i ++)
		g << Store[i] << " ";
	return 0;
}