Cod sursa(job #3288361)

Utilizator cattyAninisCatrinel catty Data 21 martie 2025 18:43:05
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string n,m;
int len,lps[2000005],i,v[1005],k,sz,j;
int main()
{
    in>>n>>m;
    for(i=1; n[i]; ++i)
    {
        if(n[i]==n[len])
            ++len,lps[i]=len;
        else if(!len)
            lps[i]=0;
        else
        {
            while(len)
            {
                len=lps[len-1];
                if(n[i]==n[len])
                {
                    ++len;
                    lps[i]=len;
                    break;
                }
            }
        }
    }
    sz=n.size();
    for(i=0,j=0; m[i]; ++i)
    {
        if(m[i]==n[j])
        {
            ++j;
            if(j==sz)
            {
                ++k;
                if(k<=1000)
                    v[k]=i+1-sz;
                j=lps[j-1];
            }
        }
        else if(j)
            j=lps[j-1],--i;
    }
    out<<k<<'\n';
    for(i=1; i<=min(1000,k); ++i)
        out<<v[i]<<' ';
}