Pagini recente » Cod sursa (job #490274) | Cod sursa (job #1936442) | Cod sursa (job #1700638) | Cod sursa (job #2047661) | Cod sursa (job #1889248)
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int nmx = 2000005;
char a[nmx],b[nmx];
int la,lb;
int p[nmx],dp[nmx];
vector <int> ans;
void citire()
{
scanf("%s", a);
la = strlen(a);
scanf("%s", b);
lb = strlen(b);
}
void prefix()
{
int i = 1, j = 0;
while(i < la)
{
if(a[i] == a[j])
{
p[i] = p[i-1] + 1;
++ i;
++ j;
}
else if(j)
j = p[j-1];
else
++ i;
}
}
void kmp()
{
int i = 0, j = 0;
while(i < lb)
{
if(b[i] == a[j])
{
dp[i+2] = dp[i+1] + 1;
++ i;
++ j;
if(j == la)
ans.push_back(i-la);
}
else if(j)
j = p[j-1];
else
++ i;
}
}
void afish()
{
printf("%d\n", ans.size());
for(vector<int>::iterator it = ans.begin(); it != ans.end(); ++it)
printf("%d ", *it);
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
citire();
prefix();
kmp();
afish();
return 0;
}