Cod sursa(job #2528870)

Utilizator WilIiamperWilliam Damian Balint WilIiamper Data 22 ianuarie 2020 18:37:08
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <fstream>
#define MAX 2000010

using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
int prsuf[MAX], indici[1005], k;
char a[MAX], b[MAX];

void kmp (){
    int i, j;
    j = 0;
    for (i = 0; b[i]; i++) {

        while (j > 0 && a[j] != b[i])
            j = prsuf[j-1];

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

        if (!a[j]) {
            k++;
            if (k <= 1001)
                indici[k] = i-j+1;
        }
    }
}

void prefix() {
    int i = 0, j;
    for (j = 1; a[j]; j++) {
        while (i > 0 && a[i] != a[j])
            i = prsuf[i-1];

        if (a[i] == a[j]) {
            i++;
            prsuf[j] = prsuf[j-1]+1;
        }
    }

}

int main()
{
    fin.getline(a, 2000005);
    fin.getline(b, 2000005);
    prefix();
    kmp();
    fout << k << "\n";
    for (int i = 1; i <= 1000 && indici[i]; i++)
        fout << indici[i] << " ";
    return 0;
}