Pagini recente » Cod sursa (job #603059) | Cod sursa (job #2807701)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define NMAX 2000005
#define MAXP 1000
char a[NMAX], b[NMAX];
int n, m, urmator[NMAX];
vector<int> v;
void init_urm(char *p)
{
int i, j;
urmator[0] = -1;
for (i=0, j=-1;i<n;i++,j++,urmator[i]=j){
while(j>=0 && p[i] != p[j]){
j = urmator[j];
}
}
}
void kmp(char *a, char *p)
{
int i, j, nr = 0;
/*for (i=0,j=0;j<n && i<m;i++, j++){
while(j >= 0 && a[i] != p[j]){
j = urmator[j];
}
if (p[j] == a[i])
j ++;
if (j == n){
nr ++;
if (v.size() < MAXP)
v.push_back(i-n);
}
}*/
i = j = 0;
while(i<m){
while(j>=0 && a[i] != p[j]){
j = urmator[j];
}
i ++;
j ++;
if (j == n){
nr ++;
if (v.size() < MAXP)
v.push_back(i - n);
}
}
fout << nr << '\n';
for (auto it : v){
fout << it << ' ';
}
}
int main() {
fin.getline(a, NMAX);
fin.getline(b, NMAX);
n = strlen(a);
m = strlen(b);
init_urm(a);
kmp(b, a);
return 0;
}