Cod sursa(job #2850260)

Utilizator traiandobrinDobrin Traian traiandobrin Data 16 februarie 2022 14:52:08
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 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-1];
                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;
}