Cod sursa(job #3321085)

Utilizator DobrePetruDobre Petru Daniel DobrePetru Data 8 noiembrie 2025 10:24:57
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string s,t;
int r,a[2000005],i,lps[2000005];
void prefixsufix(string s)
{
    int m=s.size();
    int lg=0,i=1;
    while(i<m)
    {
        if(s[lg]==s[i])
        {
            lg++;
            lps[i]=lg;
            i++;
        }
        else if(lg) lg=lps[lg-1];
        else
        {
            lps[i]=0;
            i++;
        }
    }
}
void kmp(string t,string s)
{
    int n=t.size(),m=s.size(),lg,i;
    lg=i=0;
    while(i<n)
    {
        if(t[i]==s[lg])
        {
            lg++;
            i++;
            if(lg==m)
            {
                r++;a[r]=i-m;
                lg=lps[lg-1];
            }
        }
        else if(lg) lg=lps[lg-1];
        else i++;
    }
}
int main()
{
    fin>>s>>t;
    prefixsufix(s);
    kmp(t,s);
    fout<<r<<'\n';
    for(i=1; i<=min(r,1000); i++) fout<<a[i]<<" ";

    return 0;
}