Pagini recente » Cod sursa (job #676182) | Cod sursa (job #2731675) | Cod sursa (job #1747662) | Cod sursa (job #1090813) | Cod sursa (job #1579441)
#include <fstream>
#include <string>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
int nr, V[2000010], Sol[1010];
string A, B;
void Prefix()
{
int k = 0;
for (int i = 1; i < A.size(); i ++)
{
while (k && A[i] != A[k]) k = V[k - 1];
if (A[i] == A[k]) k ++;
V[i] = k;
}
}
void KMP()
{
Prefix();
int k = 0;
for (int i = 0; i < B.size(); i ++)
{
while (k && B[i] != A[k]) k = V[k - 1];
if (B[i] == A[k]) k ++;
if (k == A.size())
{
k = V[k - 1];
if (++Sol[0] <= 1000) Sol[Sol[0]] = i - A.size() + 1;
}
}
}
int main()
{
fin >> A >> B;
KMP();
fout << Sol[0] << '\n';
Sol[0] = min(Sol[0], 1000);
for (int i = 1; i <= Sol[0]; i ++) fout << Sol[i] << ' ';
fout << '\n';
fout.close();
return 0;
}