Pagini recente » Cod sursa (job #2071930) | Cod sursa (job #1058540) | Cod sursa (job #2197344) | Cod sursa (job #2045164) | Cod sursa (job #713776)
Cod sursa(job #713776)
#include <cstdio>
#include <cstring>
#define nMax 2000100
using namespace std;
char a[nMax];
char b[nMax];
int kmp[nMax];
int n;
int m;
int StrStr[1010];
int nStrStr;
void prefix()
{
int q = 0;
for (int i = 2; i < n; ++ i){
while (q && a[q + 1] != a[i]){
q = kmp[q];
}
if (a[q + 1] == a[i]){
q ++;
}
kmp[i] = q;
}
}
void citire()
{
gets (a + 1);
gets (b + 1);
n = strlen (a + 1) + 1;
m = strlen (b + 1) + 1;
prefix();
}
void StrStrEficient()
{
int q = 0;
for (int i = 1; i < m; ++ i){
while (q && a[q + 1] != b[i]){
q = kmp[q];
}
if (a[q + 1] == b[i]){
q++;
}
if (q == n - 1){
q = kmp[q];
nStrStr ++;
if (nStrStr <= 1000){
StrStr[nStrStr] = i - n + 1;
}
}
}
}
void afis()
{
printf ("%d\n", nStrStr);
int N = (nStrStr <= 1000) ? nStrStr : 1000;
for (int i = 1; i <= N; ++ i){
printf ("%d ", StrStr [i]);
}
printf ("\n");
}
int main()
{
freopen ("strmatch.in", "r", stdin);
freopen ("strmatch.out", "w", stdout);
citire();
StrStrEficient();
afis();
return 0;
}