Pagini recente » Cod sursa (job #1228752) | Cod sursa (job #1466851) | Cod sursa (job #167247) | Cod sursa (job #2591755) | Cod sursa (job #1303833)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
const int NMAX = 2000000 + 5;
int nr;
int sol[1000 + 1];
int F[NMAX];
char s[NMAX], p[NMAX];
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
void proceseaza(char pattern[]) {
F[0] = 0;
int k = 0, m = strlen(pattern);
for (int q = 1; q < m; q++) {
while (k > 0 && pattern[k] != pattern[q]) k = F[k - 1];
if (pattern[k] == pattern[q]) k++;
F[q] = k;
}
}
void KMP(char s[], char p[]) {
int q = 0;
int n = strlen(s);
int m = strlen(p);
proceseaza(p);
for (int i = 0; i < n; i++) {
while(q > 0 && p[q] != s[i]) q = F[q - 1];
if (p[q] == s[i]) q++;
if (q == m) {
if (++nr <= 1000) {
sol[nr] = i - m + 1;
}
}
}
}
void citeste() {
f >> p >> s;
}
void scrie() {
g << nr << '\n';
for (int i = 1; i <= 1000 && i <= nr; i++) g << sol[i] << ' ';
}
int main() {
citeste();
KMP(s, p);
scrie();
return 0;
}