Cod sursa(job #3275943)

Utilizator unomMirel Costel unom Data 12 februarie 2025 08:16:29
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>

using namespace std;

ifstream in("strmatch.in");
ofstream out("strmatch.out");
int n, cnt;
string a, b, s;
int z[4000005];
int ans[1005];

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

    s = a + '$' + b + '^';
    n = s.size();

    int l = 0;
    int r = 0;
    for(int i = 1; i<n; i++)
    {
        z[i] = max(0, min(r - i, z[i - l]));

        while(s[z[i]] == s[i + z[i]])
        {
            z[i]++;
        }

        if(i + z[i] > r)
        {
            l = i;
            r = i + z[i];
        }
    }

    /*for(int i = 0; i<n; i++)
    {
        out<<s[i]<<" ";
    }
    out<<'\n';
    for(int i = 0; i<n; i++)
    {
        out<<z[i]<<" ";
    }*/

    for(int i = a.size() + 1; i<n; i++)
    {
        if(z[i] == a.size())
        {
            cnt++;

            if(cnt <= 1000)
            {
                ans[cnt] = i - a.size() - 1;
            }
        }
    }

    out<<cnt<<'\n';
    for(int i = 1; i<=min(1000, cnt); i++)
    {
        out<<ans[i]<<" ";
    }

    return 0;
}