Cod sursa(job #2387516)

Utilizator TeoDiDiaconescu Teodora TeoDi Data 24 martie 2019 19:54:51
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>
#define N 2000005

int m,n;
char A[N],B[N];
int pi[N],pos[1024];

std::ifstream fin("strmatch.in");
std::ofstream fout("strmatch.out");

void KMP()
{
	int q=0;
	pi[1]=0;
	for(int i=2;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()
{
	int q=0,p=0;
	fin.getline(A,N);
	fin.getline(B,N);
	while((A[m]>='A' && A[m]<='Z') || (A[m]>='a' && A[m]<='z') || (A[m]>='0' && A[m]<='9')) ++m;
	while((B[n]>='A' && B[n]<='Z') || (B[n]>='a' && B[n]<='z') || (B[n]>='0' && B[n]<='9')) ++n;
	for (int i=m;i;--i) A[i]=A[i-1]; A[0] = ' ';
	for (int i = n; i; --i) B[i] = B[i-1]; B[0] = ' ';
	KMP();
	for (int i=1;i<=n;++i)
	{
		while(q&&A[q+1]!=B[i]) q=pi[q];
		if (A[q+1]==B[i]) ++q;
		if(q==m)
		{
			q=pi[m];
			++p;
			if (p<=1000)
				pos[p]=i-m;
		}
	}
	fout<<p<<'\n';
	for (int i=1;i<=std::min(p,1000);++i)
		fout<<pos[i]<<' ';
	return 0;
}