Cod sursa(job #2591839)

Utilizator victorzarzuZarzu Victor victorzarzu Data 31 martie 2020 15:00:05
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <bits/stdc++.h>

using namespace std;

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

string A,B;
int n, m, q;
int pi[20000005];
vector<int> res;

void Read()
{
	f>>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);

	A.insert(0, " ");
	B.insert(0, " ");

	f.close();
}

void compute()
{
	q = 0;
	pi[0] = 1;

	for(int i = 2;i <= m;++i)

	{
		while(q > 0 && A[q + 1] != A[i])
			q = pi[q];
		if(A[q + 1] == A[i])
			++q;
		pi[i] = q;
	}
}

void KMP()
{
	q = 0;
	for(int 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)
		{
			q = pi[q];
			if(res.size() < 1000)
				res.push_back(i - m);
		}
	}
}

void Print()
{
	g<<res.size()<<'\n';
	for(vector<int>::iterator it = res.begin();it != res.end();++it)
		g<<*it<<" ";
	g.close();
}

int main()
{
	Read();
	compute();
	KMP();
	Print();
	return 0;
}