Cod sursa(job #3289137)

Utilizator andrei1232008nicolae andrei andrei1232008 Data 25 martie 2025 19:48:16
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string s,t;
int i;
int lps[2000005];
vector <int> sol;
void dolps()
{
    int len=0,i=1;
    lps[0]=0;
    while(i<t.size())
    {
        if(t[i]==t[len])
        {
            len++;
            lps[i]=len;
            i++;
        }
        else
        {
            if(len!=0)
            {
                len=lps[len-1];
            }
            else
            {
                lps[i]=0;
                i++;
            }
        }
    }
}
void dokmp()
{
    int i=0,j=0,n=s.length(),m=t.length();
    while(i<n)
    {
        if(s[i]==t[j])
        {
            i++;j++;
            if(j==m){sol.push_back(i-j);
            j=lps[j-1];}
        }
        else
        {
            if(j!=0)
            {
                j=lps[j-1];
            }
            else i++;
        }
    }
}
int main()
{
    fin>>t>>s;
    dolps();
    dokmp();
    fout<<sol.size()<<'\n';
    for(auto e=0;e<sol.size();e++)
    {
        if(e>1000)return 0;
        fout<<sol[e]<<" ";
    }
    return 0;
}