Pagini recente » Cod sursa (job #397698) | Cod sursa (job #2201169) | Cod sursa (job #2980089) | Cod sursa (job #684498) | Cod sursa (job #2734664)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000001], b[2000001];
int pi[50001], i, cnt;
queue<int> Q;
void kmp()
{
int k = 0;
pi[1] = 0;
for (i = 2; i < strlen(a); i++)
{
while(k>0 && a[k+1] != a[i])
k = pi[k];
if (a[k+1] == a[i])
k++;
pi[i] = k;
}
int q = 0;
for (i = 1; i < strlen(b); i++)
{
while (q > 0 && a[q+1]!= b[i])
q = pi[q];
if (a[q+1] == b[i])
q++;
if (q == strlen(a)-1)
{
Q.push(i-strlen(a)+1);
cnt++;
}
if (cnt >= 1000) return;
}
}
int main()
{
fin >> a+1 >> b+1;
a[0] = ' ';
b[0] = ' ';
kmp();
fout << cnt << "\n";
while (! Q.empty())
{
fout << Q.front() << " ";
Q.pop();
}
return 0;
}