Cod sursa(job #3155207)

Utilizator BuzdiBuzdugan Rares Andrei Buzdi Data 7 octombrie 2023 17:36:16
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>

using namespace std;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

const int NMAX = 2e6;

string a, b;
int LPS[2 * NMAX + 2];
int Answer[1001], ind;
int secvente;

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

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

    a = a + "#" + b;

    LPS[0] = 0;
    for(int i = 1; i < (int) a.size(); i++)
    {
        int j = LPS[i - 1];
        while(j > 0 && a[j] != a[i])
            j = LPS[j - 1];

        if(a[j] == a[i])
            j++;

        LPS[i] = j;

        if(LPS[i] == n)
        {
            secvente++;
            if(ind < 1000)
                Answer[++ind] = i - 2 * n;
        }
    }

    cout << secvente << '\n';
    for(int i = 1; i <= ind; i++)
        cout << Answer[i] << ' ';


    return 0;
}