Pagini recente » Cod sursa (job #1634428) | Cod sursa (job #1690268) | Cod sursa (job #384961) | Cod sursa (job #2261981) | Cod sursa (job #1830800)
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX 2000005
using namespace std;
char pattern[MAX];
int indPattern[MAX];
char text[MAX];
int sol[MAX];
int nr, l;
void buildPattern()
{
int i=1, j=0;
indPattern[0] = 0;
int length = strlen(pattern);
while(indPattern[length-1] == -1 && i < length)
{
if (pattern[i] != pattern[j])
{
j = indPattern[j-1];
if (j == 0 && pattern[i] != pattern[j])
i++;
}
else
indPattern[i] = j+1, i++, j++;
}
for (int i=0; i<strlen(pattern); i++)
if (indPattern[i] == -1)
indPattern[i] = 0;
}
void solve()
{
int i=0, j = 0;
int length = strlen(text);
while(i < length)
{
if (j == strlen(pattern) - 1 && pattern[j] == text[i])
sol[l++] = i - strlen(pattern) + 1;
if (text[i] == pattern[j])
i++, j++;
else
{
j = indPattern[j-1];
if (j == 0 && text[i] != pattern[j])
i++;
}
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
memset(indPattern, -1, sizeof(indPattern));
gets(pattern);
gets(text);
buildPattern();
solve();
printf("%d\n", l);
if (l > 1000)
l = 1000;
for (int i=0; i<l; i++)
printf("%d ", sol[i]);
return 0;
}