Cod sursa(job #2458575)

Utilizator minecraft3Vintila Valentin Ioan minecraft3 Data 21 septembrie 2019 08:58:42
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <bits/stdc++.h>
#define N 2000 + 5

using namespace std;

vector<int> v;
ofstream fout("strmatch.out");

char A[N], B[N];
int pi[N];

void calc_pi() {
    int i = 1, j = 1;
    pi[1] = 0;
    while(A[++j])
        if(A[i] == A[j]) pi[j] = i, ++i;
        else if(i != 1) i = 1, --j;
}

void calc_kmp() {
    int n = 0, i = 1, j = 0;
    do {
        if(B[i] == A[j+1]) {
            ++j;
            if(!A[j+1]) {
                ++n;
                if(v.size() < 1000) v.push_back(i - j);
                j = pi[j];
            }
        } else if(j) {
            do {
                j = pi[j];
            } while(B[i] != A[j+1] && j);
            --i;
        }
    } while(B[++i]);

    (fout << n).put('\n');
    for(int x : v)
        (fout << x).put(' ');
}

int main() {
    ifstream fin("strmatch.in");

    fin >> (A+1) >> (B+1);

    calc_pi(); calc_kmp();
    //for(int i = 1; A[i]; ++i)
    //    cout << A[i] << ": " << pi[i] << endl;
}