Cod sursa(job #3280741)

Utilizator Anul2024Anul2024 Anul2024 Data 27 februarie 2025 14:44:08
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
char s1[2000005],s2[2000005],s[4000005];
int n,m,st,dr,k,sol[1001],z[4000005];
int main()
{
    fin>>s1>>s2;
    strcat (s+1,s1);
    m=strlen (s+1);
    strcat (s+1,"*");
    strcat (s+1,s2);
    n=strlen (s+1);
    z[1]=n;
    for (int i=1; i<=n; i++)
    {
        if (i<=dr)
            z[i]=min (z[i-st+1],dr-i+1);
        while (i+z[i]<=n&&s[i+z[i]]==s[z[i]+1])
            z[i]++;
        if (i>m+1&&z[i]==m)
        {
            k++;
            if (k<=1000)
                sol[k]=i-(m+2);
        }
        if (i+z[i]-1>dr)
        {
            dr=i+z[i]-1;
            st=i;
        }
    }
    fout<<k<<"\n";
    for (int i=1; i<=k; i++)
        fout<<sol[i]<<" ";
    return 0;
}