Pagini recente » Cod sursa (job #1478198) | Cod sursa (job #1088415) | Cod sursa (job #330967) | Cod sursa (job #1355441) | Cod sursa (job #1579439)
#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';
for (int i = 1; i <= Sol[0]; i ++) fout << Sol[i] << ' ';
fout << '\n';
fout.close();
return 0;
}