Pagini recente » Cod sursa (job #3159796) | Borderou de evaluare (job #713020) | Cod sursa (job #505404) | Cod sursa (job #2242403) | Cod sursa (job #3141905)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000002], b[2000002];
char A[2000002], B[2000002];
int k = 0, sol[1001], p[2000001], l = 0;
int n, m;
int main()
{
fin >> A >> B;
strcpy(a + 1, A);
strcpy(b + 1, B);
p[1] = 0;
n = strlen(a + 1);
m = strlen(b + 1);
for (int i = 2; i <= n; i++)
{
while (l != 0 && a[i] != a[l + 1])
l = p[l];
if (a[i] == a[l + 1])
l++;
p[i] = l;
}
l = 0;
for (int i = 1; i <= m; i++)
{
while (l != 0 && b[i] != a[l + 1])
l = p[l];
if (b[i] == a[l + 1])
l++;
if (l == n)
{
k++;
if (k <= 1000)
sol[k] = i - n + 1;
l = p[l];
}
}
fout << k << '\n';
if (k > 1000)
k = 1000;
for (int i = 1; i <= k; i++)
fout << sol[i] - 1 << " ";
}