Cod sursa(job #3304065)

Utilizator unomMirel Costel unom Data 20 iulie 2025 11:27:24
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream in("strmatch.in");
ofstream out("strmatch.out");
int n, m, ans;
string a, b;
int lps[2000005];
vector<int> poz;

void build_lps()
{
    int len = 0;
    int i = 2;

    while(i <= n)
    {
        if(a[i] == a[len + 1])
        {
            len++;
            lps[i] = len;
            i++;
        }
        else
        {
            if(len != 0)
            {
                len = lps[len];
            }
            else
            {
                lps[i] = 0;
                i++;
            }
        }
    }
}

int main()
{
    in>>a>>b;

    n = a.size();
    m = b.size();

    a = '$' + a;
    b = '$' + b;

    build_lps();

//    for(int i = 1; i<=n; i++)
//    {
//        out<<lps[i]<<" ";
//    }

    int i = 0;
    int j = 1;
    while(j <= m)
    {
        if(b[j] == a[i + 1])
        {
            j++;
            i++;

            if(i == n)
            {
                ans++;

                if(poz.size() < 1000)
                {
                    poz.push_back(j - 1);
                }

                i = lps[i];
            }
        }
        else
        {
            if(i == 0)
            {
                j++;
            }
            else
            {
                i = lps[i];
            }
        }
    }

    out<<ans<<'\n';
    for(auto it: poz)
    {
        out<<it - n<<" ";
    }

    return 0;
}