Pagini recente » Cod sursa (job #1113725) | Cod sursa (job #2623876) | Cod sursa (job #1614928) | Cod sursa (job #2684255) | Cod sursa (job #1830792)
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX 2000000
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;
while(indPattern[strlen(pattern)-1] == -1 && i < strlen(pattern))
{
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;
//for (int i=0; i<strlen(pattern); i++)
//cout<<indPattern[i];
}
void solve()
{
int i=0, j = 0;
while(i < strlen(text))
{
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);
for (int i=0; i<l; i++)
printf("%d ", sol[i]);
return 0;
}