Pagini recente » Cod sursa (job #2744522) | Cod sursa (job #619899) | Cod sursa (job #2707786) | Cod sursa (job #1872202) | Cod sursa (job #1313311)
#include<cstdio>
#include<cstring>
using namespace std;
const int NMAX = 2000000;
char a[NMAX + 2], b[NMAX + 2];
int n, m;
int p[NMAX + 2], poz[1002];
int prefix(char *s)
{
int k = 0;
p[0] = 0;
for(int i = 1; i < n; i++)
{
while(k > 0 && s[i] != s[k])
k = p[k - 1];
if(s[k] == s[i])
++k;
p[i] = k;
}
}
int kmp(char *a, char *b)
{
prefix(a);
int k = 0, cnt = 0;
for(int i = 0; i < m; i++)
{
while(k > 0 && a[k] != b[i])
k = p[k - 1];
if(a[k] == b[i])
k ++;
if(k == n)
{
cnt ++;
if(poz[0] < 1000)
poz[++poz[0]] = i - n + 1;
}
}
return cnt;
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w",stdout);
gets(a);
n = strlen(a);
gets(b);
m = strlen(b);
printf("%d\n", kmp(a, b));
for(int i = 1; i <= poz[0]; i++)
printf("%d ", poz[i]);
return 0;
}