Pagini recente » Cod sursa (job #425731) | Cod sursa (job #81133) | Cod sursa (job #257850) | Rezultatele filtrării | Cod sursa (job #831725)
Cod sursa(job #831725)
//
// 005.3.cc
// 005.1
//
// Created by Radu Brumariu on 12/2/12.
// Copyright (c) 2012 Radu Brumariu. All rights reserved.
//
#define MAXN 2000001
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstring>
int* compute_prefix(const char* P, int m);
int main(void) {
char* P = new char[MAXN];
char* T = new char[MAXN];
P[0] = T[0] = ' ';
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s %s", (P+1), (T+1));
int n = strnlen(T+1, MAXN);
int m = strnlen(P+1, MAXN);
int* results = new int[MAXN];
if(m > n) {
std::cout << "0" << std::endl;
return 0;
}
int* pi = compute_prefix(P, m);
int q = 0;
int cnt = 0;
for (int i = 1; i <= n; i++) {
while (q>0 && P[q+1] != T[i]) {
q = pi[q];
}
if (P[q+1] == T[i]) {
q++;
}
if (q == m) {
q = pi[m];
results[cnt++] = i-m;
}
}
std::cout << cnt << std::endl;
for(int i = 0; (i < cnt && i < 1000); i++){
std::cout << results[i] << " ";
}
std::cout << std::endl;
delete [] pi;
delete [] P;
delete [] T;
return 0;
}
int* compute_prefix(const char* P, int m){
int *pi = new int[m+1];
int k = 0;
pi[1] = 0;
for (int q = 2; q<=m; q++) {
while (k>0 && P[k+1] != P[q]) {
k = pi[k];
}
if (P[k+1] == P[q]) {
k++;
}
pi[q] = k;
}
return pi;
}