Cod sursa(job #837077)

Utilizator Theorytheo .c Theory Data 17 decembrie 2012 11:41:09
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include<fstream>
#include<string.h>
#define nmax 2000009
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int N;
char s[nmax], p[nmax];
int H[nmax], ret[1005];
int nr;
void read(){
    fin >> p + 1;
    N = strlen(p + 1);
    fin >> s + 1;
}
void prelucrare(){
    int q = 0;
    for(int i = 2; p[i] ; i++){
        while(q > 0 && p[i] != p[q + 1])
            q = H[q];
        if(p[i] == p[q + 1])
            q++;
        H[i] = q;

    }
}
void solve(){
    int q = 0;
    for(int i = 1; s[i]; i++){
        while(q && s[i] != p[q + 1])
            q = H[q];
        if(s[i] == p[q + 1])
            q++;
        if(q == N){
            nr++;
            if(nr <= 1000)
                ret[nr] = i - q;
            q = H[N];
        }
    }
    fout << nr<<'\n';
    for(int i = 1; i <= min(nr,1000); i++)
        fout << ret[i] <<" " ;
}
int main()
{
    read();
    prelucrare();
    solve();
    fin.close();
    return 0;

}