Cod sursa(job #3288764)

Utilizator alexdraguAlexandru Dragu alexdragu Data 24 martie 2025 10:31:04
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string s,t;
int n,m,len,lps[2000005],i,j,cnt,v[2000005];
int main()
{
    cin>>t>>s;
    n=s.size();
    m=t.size();
    len=0;
    lps[0]=0;
    i=1;
    while(i<m)
    {
        if(t[i]==t[len])
        {
            len++;
            lps[i]=len;
            i++;
        }
        else
        {
            if(len!=0) len=lps[len-1];
            else
            {
                lps[i]=0;
                i++;
            }
        }
    }
    i=0;j=0;
    while(i<n)
    {
        if(s[i]==t[j])
        {
            i++;
            j++;
            if(j==m)
            {
                cnt++;
                v[cnt]=i-m;
                j=lps[j-1];
            }
        }
        else
        {
            if(j!=0) j=lps[j-1];
            else i++;
        }
    }
    cout<<cnt<<'\n';
    for(i=1;i<=cnt;i++) cout<<v[i]<<' ';
    return 0;
}