Pagini recente » Cod sursa (job #2451694) | Cod sursa (job #1561128) | Cod sursa (job #1366714) | Cod sursa (job #1806885) | Cod sursa (job #2467540)
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int N = 2e6+5;
int pi[N],sol[1005];
char a[N],b[N];
int n,m;
void PiTable()
{
int q = 0;
pi[1] = 0;
for (int i = 2; i<=n; i++)
{
while (a[i]!=a[q+1] && q>0)
q = pi[q];
if (a[i] == a[q+1])
q++;
pi[i] = q;
}
}
int main()
{
in >> (a+1) >> (b+1);
n = strlen(a+1); m = strlen(b+1);
PiTable();
int q = 0, ans = 0;
for (int i = 1; i<=m; i++)
{
while (b[i]!=a[q+1] && q>0)
q = pi[q];
if (b[i] == a[q+1])
q++;
if (q == n)
{
ans++;
if (ans<=1000)
sol[ans] = i-n;
}
}
out << ans << "\n";
for (int i = 1; i<=min(ans,1000); i++)
out << sol[i] << " ";
}