Cod sursa(job #2462291)

Utilizator zdavid112zIon David-Gabriel zdavid112z Data 26 septembrie 2019 23:27:00
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>

using namespace std;

char str[4000020];
int lpattern, ltext, lstr;
int z[4000020];
int numMatches, matches[1010];

void reload(int i, int& l, int& r)
{
    l = i;
    r = max(r, i);
    while(r < lstr && str[r - l] == str[r])
    {
        r++;
    }
    z[i] = r - l;
    r--;
}

void match()
{
    int l = 0, r = 0;
    for(int i = 1; i < lstr; i++)
    {
        if(i > r)
        {
            reload(i, l, r);
        }
        else
        {
            int k = i - l;
            if(z[k] <= r - i)
                z[i] = z[k];
            else reload(i, l, r);
        }
        if(z[i] == lpattern)
        {
            if(numMatches < 1000)
                matches[numMatches] = i - lpattern - 1;
            numMatches++;
        }
    }
}

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    cin >> str;
    lpattern = strlen(str);
    str[lpattern] = '$';
    cin >> (str + lpattern + 1);
    ltext = strlen(str + lpattern + 1);
    lstr = lpattern + ltext + 1;
    match();
    cout << numMatches << '\n';
    for(int i = 0; i < min(numMatches, 1000); i++)
        cout << matches[i] << " ";
    return 0;
}