Cod sursa(job #1799462)

Utilizator satzaFoldesi Richard satza Data 6 noiembrie 2016 13:13:15
Problema Potrivirea sirurilor Scor 32
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

ifstream be("strmatch.in");
ofstream ki("strmatch.out");
int n,m,nr,pi[2000000],k,i,p[2000000];
char a[2000001],b[20000001];

void set_pi(){
    k = 0; pi[0] = k;
    for(i = 1; i <= m; i++){
        while(k>0 and a[i] != a[k])
            k = pi[k-1];

        if(a[i] == a[k])
            k = k + 1;
        pi[i] = k;
    }
}

int main()
{
    be >> a >> b;


    n = strlen(b) - 1; m = strlen(a) - 1;
    if(m == 0){
        nr = 0;
        for(i = 0; i <= n && nr < 1000; ++i){
            if(b[i] == a[0]) {
                nr = nr + 1;
                p[nr] = i;
            }
        }
    }
    else {
        k = 0; nr = 0;
        set_pi();
        for(i = 0; i <= n && nr < 1000; ++i){
            while(k > 0 && b[i] !=a[k]){
                k = pi[k-1];
            }

            if(b[i] == a[k]) k = k + 1;

            if(k == m+1){
                nr = nr + 1;
                p[nr] = i - m;
                k= pi[k-1];
            }
        }
    }
    ki << nr << "\n";
    for(i = 1; i <= nr; i++) ki << p[i] << " ";
    return 0;
}