Cod sursa(job #2871199)

Utilizator traiandobrinDobrin Traian traiandobrin Data 13 martie 2022 07:09:10
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <fstream>

#include <cstring>

using namespace std;

ifstream cin("strmatch.in");

ofstream cout("strmatch.out");

const int maxn=2e6+55;

int lsp[maxn];

char pat[maxn],txt[maxn];

int z[maxn];

int ans[maxn],cnt=0;

int main()

{

int l1,l2;

cin>>(pat+1);

cin>>(txt+1);

l1=strlen(pat+1);

l2=strlen(txt+1);

int q = 0;

int len=0;

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

	{ int nlen=max(len,1);

		if(pat[len+1]==pat[i])

{

++len;

lsp[i]=len;

}

else

{

if(len)

{

len=lsp[len];

i--;

}

else

{

len=0;

lsp[i]=0;

}

}

	}/*for(int i=1;i<=l1;++i)

	 cout<<lsp[i]<<" ";*/

int i1,i2;

i1=i2=1;

for(int i=1;i<=l2;++i)

{

if(pat[i1]==txt[i])

{

i1++;

if(i1>l1)

{

i1=lsp[l1]+1;

ans[++cnt]=i-l1;

}

}

else

{ if(i1>1){

i1=lsp[i1-1]+1;

i--;}

else

i1=1;

}

}

cout<<cnt<<'\n';

for(int i=1;i<=min(1000,cnt);++i)

cout<<ans[i]<<" ";

return 0;

}