Pagini recente » Istoria paginii runda/oji2008x | Istoria paginii runda/wellcodesimulareclasa11-12-12martie | Cod sursa (job #322509) | Cod sursa (job #1865538) | Cod sursa (job #463922)
Cod sursa(job #463922)
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
char a[2000001], b[2000001];
int prefix[2000001];
int pos[1001], n;
void make_prefix()
{
int k = -1;
prefix[0] = -1;
for (int i = 1; i < strlen(a); ++i)
{
while (k != -1 && a[k + 1] != a[i])
k = prefix[k];
if (a[k + 1] == a[i])
++k;
prefix[i] = k;
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
fgets(a, sizeof(a), stdin);
fgets(b, sizeof(b), stdin);
a[strlen(a) - 1] = '\0';
b[strlen(b) - 1] = '\0';
make_prefix();
int ok = -1;
for (int i = 0; i < strlen(b); ++i)
{
while (ok != -1 && a[ok + 1] != b[i])
ok = prefix[ok];
if (a[ok + 1] == b[i])
++ok;
if (ok == strlen(a) - 1)
{
++n;
if (n <= 1000)
pos[n] = i - strlen(a) + 1;
}
}
printf("%d \n", n);
for (int i = 1; i <= min(n, 1000); ++i)
printf("%d ", pos[i]);
}