Cod sursa(job #3179369)

Utilizator BOSSSTEFANPetrescu Ioan Stefan BOSSSTEFAN Data 3 decembrie 2023 15:35:37
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("strmatch.in");
ofstream  cout("strmatch.out");
const long long nmax=2e6+1;
char pattern[nmax*2],txt[nmax];
int dp[nmax*2],poz[1001];
int main()
{
    cin>>pattern>>txt;
    int m=strlen(pattern),n=strlen(txt),i,rez=0,l=0,r=0,t,j;
    strcat(pattern,"$");
    strcat(pattern,txt);
    n+=m+1;
    for(i=1;i<n;i++)
    {
        if(i>r)
        {
            for(t=0,j=i;j<n&&pattern[j]==pattern[t];t++,j++);
            l=i;
            r=j-1;
            dp[i]=r-l+1;
        }
        else
        {
            if(dp[i-l]<r-i+1)
                dp[i]=dp[i-l];
            else
            {
                l=i;
                while(pattern[r]==pattern[r-l]&&r<n)
                    r++;
                r--;
                dp[i]=r-l+1;
            }
        }
        if(dp[i]==m)
        {
            rez++;
            if(rez<=1000)
                poz[rez]=i-m-1;
        }
    }
    cout<<rez<<'\n';
    rez=min(rez,1000);
    for(i=1;i<=rez;i++)
        cout<<poz[i]<<" ";
    return 0;
}