Cod sursa(job #2849695)

Utilizator traiandobrinDobrin Traian traiandobrin Data 15 februarie 2022 15:51:14
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 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 l,r;
    l=r=0;
    for(int i=2; i<=l1; ++i)
    {
        if(i>r)
        {
            l=r=i;
            while(r<=l1&&pat[r-l+1]==pat[r])
            {
                lsp[r]=max(lsp[r],r-l+1);
                ++r;
            }
            r--;
            z[i]=r-l+1;
        }
        else
        {
            if(z[i-l+1]+i-1<r)
                z[i]=z[i-l+1];
            else
            {   r=l=i;
                while(r<=l1&&pat[r-l+1]==pat[r])
                {
                    lsp[r]=max(lsp[r],r-l+1);
                    ++r;
                }
                r--;
                z[i]=r-l+1;
            }
        }
        lsp[r]=max(lsp[r],r-l+1);
    }
  //  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=max(1,lsp[i1]+1);
            else
            {
                ++i1;
                if(i1>l1)
                {
                    ans[++cnt]=i-l1+1;
                    i1=max(lsp[l1]+1,1);
                }
            }
        }
        cout<<cnt<<'\n';
    for(int i=1;i<=min(1000,cnt);++i)
        cout<<ans[i]-1<<" ";
    return 0;
}