Pagini recente » Cod sursa (job #2576634) | Cod sursa (job #1178934) | Cod sursa (job #243486) | Cod sursa (job #2439634) | Cod sursa (job #2589312)
#include <iostream>
#include <string.h>
#include <algorithm>
#include <fstream>
using namespace std;
void prefix(char t[], int pi[]) {
int n = strlen(t);
int k = 0;
pi[0] = 0;
for (int i = 1; i < n; i++) {
k = pi[i - 1];
while ((k > 0) && (t[k] != t[i]))
{
k = pi[k-1];
}
if (k == 0) {
if (t[k] != t[i])
pi[i] = 0;
else
pi[i] = 1;
}
else
pi[i] = k + 1;
}
int i;
}
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int v[2000001], poz[2000001];
void KMP(char s[], char t[]) {
int n = strlen(s);
int m = strlen(t);
int q = 0;
s[n] = '#';
s[n + 1] = NULL;
int i, j;
for (i = n + 1, j = 0; j <= m; i++, j++)
s[i] = t[j];
prefix(s, v);
m = strlen(s);
int nr = 0;
for(int i=2*n;i<m;i++)
if (v[i] == n) {
nr++;
poz[nr] = i-2*n;
}
g << nr << endl;
for (int i = 1; i <= min(1000,nr); i++)
g << poz[i] << " ";
}
char a[2000001], b[2000001];
int main()
{
f >> a;
f >> b;
KMP(a, b);
}