Pagini recente » Cod sursa (job #154250) | Cod sursa (job #787960) | Cod sursa (job #594651) | Cod sursa (job #1229616) | Cod sursa (job #1399556)
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
char s[2000005], t[2000005];
int p[2000005], n;
vector<int>sol;
void prefix()
{
int k = 0, i;
n = strlen(s + 1);
for(i = 2; i <= n; i++)
{
while(k && s[k + 1] != s[i])k = p[k];
if(s[i] == s[k + 1])
k++;
p[i] = k;
}
}
void kmp()
{
int k = 0, m = strlen(t + 1), i;
for(i = 1; i <= m; i++)
{
while(k && s[k + 1] != t[i])k = p[k];
if(t[i] == s[k + 1])
k++;
if(k == n)
sol.pb(i - n);
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s%s", s + 1, t + 1);
prefix();
kmp();
printf("%d\n", sol.size());
int i = 0;
for(auto it : sol)
{
printf("%d ", it);
i++
if (i == 1000)
return 0;
}
return 0;
}