Pagini recente » Cod sursa (job #1377216) | Cod sursa (job #2627097) | Cod sursa (job #1776804) | Cod sursa (job #2578488) | Cod sursa (job #1792123)
#include <bits/stdc++.h>
#define Dim 2000002
#define Lim 1002
FILE *fin = freopen("strmatch.in", "r", stdin);
FILE *fout = freopen("strmatch.out", "w", stdout);
using namespace std;
char pattern[Dim], text[Dim], sol[Lim];
int F[Dim], n, m;
void internal_rules()
{
int j;
F[0] = F[1] = 0;
for(int i = 2; i <= n; ++ i)
{
j = F[i - 1];
for( ; ; )
{
/// check to see if the last ch of string(prefix) i
/// expands the current candidate
if(pattern[i - 1] == pattern[j])
{
F[i] = j + 1;
break;
}
if(j == 0)
{
F[i] = 0;
break;
}
j = F[j];
}
}
}
void KMP()
{
int i = 0, j = 0;
internal_rules();
for( ; ; )
{
if(j == m) break;
/// if the current ch of the text
/// expands the current match
if(text[j] == pattern[i])
{
++ i; /// change current state of automaton
++ j; /// next character
if(i == n && sol[0] < Lim)
sol[++ sol[0]] = j - n;
if(sol[0] == Lim) return;
}
else if(i > 0) i = F[i];
else ++ j;
}
}
void write()
{
printf("%d\n", sol[0]);
for(int i = 1; i <= sol[0]; ++ i)
printf("%d ", sol[i]);
}
int main()
{
gets(pattern);
n = strlen(pattern);
gets(text);
m = strlen(text);
KMP();
write();
return 0;
}