Cod sursa(job #3342013)

Utilizator BidonTurtitBezdedan Eric BidonTurtit Data 22 februarie 2026 14:20:28
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define NMax 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char sir[NMax],s[NMax];
int t[NMax],sol=0,rez[1005];

void prefix(char s[])
{
    int j=0;
    t[0]=0;
    for(int i=1; s[i]; i++)
    {
        while(s[i]!=s[j] && j!=0)
            j=t[j-1];
        if(s[i]==s[j])
            j++;
        t[i]=j;
    }
}
int main()
{
    fin>>s>>sir;
    prefix(s);
    int j=0;
    for(int i=0; sir[i]; i++)
    {
        while(sir[i]!=s[j] && j!=0)
            j=t[j-1];
        if(sir[i]==s[j])
            j++;
        if(j==strlen(s))
        {
            sol++;
            if(sol<=1000)
                rez[sol]=i-j+1;
            j=t[j-1];
        }
    }
    fout<<sol<<"\n";
    for(int i=1; i<=min(sol,1000); i++)
    {
        fout<<rez[i]<<" ";
    }
    return 0;
}