Cod sursa(job #1645180)

Utilizator serbanSlincu Serban serban Data 10 martie 2016 11:22:02
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

char a[2000005]; int na;
char b[2000005]; int nb;

vector<int> ans; int nr = 0;

int pi[2000005];
void prefix() {
    int k = 0; pi[1] = 0;
    for(int i = 2; i <= na; i ++) {
        while(k && a[i] != a[k + 1]) k = pi[k];
        if(a[i] == a[k + 1]) k ++;
        pi[i] = k;
    }
}

void caut() {
    int k = 0;
    for(int i = 1; i <= nb; i ++) {
        while(k && b[i] != a[k + 1]) k = pi[k];
        if(b[i] == a[k + 1]) k ++;
        if(k == na) {
            if(ans.size() > 1000) nr ++;
            else nr ++, ans.push_back(i - na);
            k = pi[na];
        }
    }
}

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    gets(a + 1); gets(b + 1);
    na = strlen(a + 1);
    nb = strlen(b + 1);
    prefix();
    caut();

    cout << nr << "\n";
    for(int i = 0; i < ans.size(); i ++) cout << ans[i] << " ";
    cout << "\n";
    return 0;
}