Cod sursa(job #2849709)

Utilizator traiandobrinDobrin Traian traiandobrin Data 15 februarie 2022 16:33:58
Problema Potrivirea sirurilor Scor 22
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 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;

	for (int i = 2; i <= l1; ++i)
	{
		while (q && pat[q+1] != pat[i])
			q = lsp[q];
		if (pat[q+1] == pat[i])
			++q;
		lsp[i] = q;
	}
        int i1,i2;
        i1=i2=1;
        for(int i=1;i<=l2;++i)
        {
            while(i1&&pat[i1+1]!=txt[i])
                i1=lsp[i1-1];
            if(pat[i1+1]==txt[i])
            {
                ++i1;
                if(i1==l1)
                {
                    ans[++cnt]=i-l1;
                    i1=lsp[l1];
                }
            }
        }
        cout<<cnt<<'\n';
    for(int i=1;i<=min(1000,cnt);++i)
        cout<<ans[i]<<" ";
    return 0;
}