Cod sursa(job #3278815)

Utilizator Tudor_CCTudor Cocu Tudor_CC Data 20 februarie 2025 20:06:54
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <bits/stdc++.h>

using namespace std;

string s,a;

int lps[2000005];

vector <int> v;

int main()
{
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    cin>>a>>s;
    int i=1,j=0;
    while(i<a.size())
    {
        if(a[i]==a[j])
        {
            ++j;
            lps[i]=j;
            ++i;
        }
        else
        {
            if(j>0)
            {
                j=lps[j-1];
            }
            else
            {
                lps[i]=0;
                ++i;
            }
        }
    }
    j=0;
    for(int i=0;i<s.size();++i)
    {
        while(j>0 && s[i]!=a[j])
        {
            j=lps[j-1];
        }
        if(s[i]==a[j])
        {
            ++j;
        }
        if(j==a.size())
        {
            v.push_back(i-a.size()+1);
            j=lps[j-1];
        }
    }
    cout<<v.size()<<"\n";
    for(int i=0;i<v.size();++i)
    {
        cout<<v[i]<<" ";
    }
    return 0;
}