Cod sursa(job #2263576)

Utilizator SemetgTemes George Semetg Data 18 octombrie 2018 20:11:00
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include <iostream>
using namespace std;

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

const int N_MAX = 2000005;
char a[N_MAX], b[N_MAX];
int n, m;
int pref_suf[N_MAX];
int rez[N_MAX], k;

void creaza_pref_suf() {
    pref_suf[0] = 0;
    int lg { 0 };
    
    for (int i { 1 }; i < n;) {
        if (a[i] == a[lg]) {
            pref_suf[i++] = ++lg;
        } else {
            if (lg) {
                lg = pref_suf[lg - 1];
            } else {
                pref_suf[i] = 0;
                ++i;
            }
        }
    }
}

void KMP() {
    for (int i { 0 }, j { 0 }; i < m;) {
        if (b[i] == a[j]) {
            ++i;
            ++j;
        }
        
        if (j == n)
            rez[k++] = i - j;
        
        if (i < m && a[j] != b[i]) {
            if (j)
                j = pref_suf[j - 1];
            else
                ++i;
        }
    }
}

int main() {
    in.getline(a, N_MAX);
    in.getline(b, N_MAX);
    
    n = strlen(a);
    m = strlen(b);
    
    if (n > m) {
        out << 0;
        return 0;
    }
    
    creaza_pref_suf();
    KMP();
    out << k << '\n';
    k = min(1000, k);
    
    for (int i { 0 }; i < k; ++i)
        out << rez[i] << ' ';
}