Cod sursa(job #2462283)

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

using namespace std;

char a[2000010], b[2000010];
int la, lb;
int v[2000010];
int numMatches, matches[1010];

void preprocess()
{
    int k = -1;
    v[0] = -1;
    for(int i = 1; i < lb; i++)
    {
        while(k != -1 && b[i] != b[k + 1])
            k = v[k];
        if(b[i] == b[k + 1])
            k++;
        v[i] = k;
    }
}

void match()
{
    int k = -1;
    for(int i = 0; i < la; i++)
    {
        while(k != -1 && a[i] != b[k + 1])
            k = v[k];
        if(a[i] == b[k + 1])
            k++;
        if(k == lb - 1)
        {
            if(numMatches < 1000)
                matches[numMatches] = i - lb + 1;
            numMatches++;
        }
    }
}

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    cin >> b >> a;
    la = strlen(a);
    lb = strlen(b);
    preprocess();
    match();
    cout << numMatches << '\n';
    for(int i = 0; i < min(numMatches, 1000); i++)
        cout << matches[i] << " ";
    return 0;
}