Pagini recente » Cod sursa (job #677637) | Cod sursa (job #2760893) | Cod sursa (job #2145302) | Cod sursa (job #2115989) | Cod sursa (job #2038424)
#include <iostream>
#include <fstream>
#include <string.h>
#include <vector>
#define NMAX 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int a, b, f, cnt;
char A[NMAX], B[NMAX], S[NMAX];
vector <int> rsp;
int main()
{
fin >> A + 1 >> B + 1;
a = strlen(A + 1);
b = strlen(B + 1);
S[0] = -1;
S[1] = 0;
for (int i = 2; i <= a; i++)
{
int prv = i - 1;
char ch = A[i];
while (S[prv] != -1 && A[S[prv] + 1] != ch)
prv = S[prv];
S[i] = S[prv] + 1;
}
for (int i = 1; i <= b; i++)
{
while (f != -1)
if (A[f + 1] == B[i])
break;
else f = S[f];
if (f == -1)
f = 0;
else{
f++;
if (f == a)
{
rsp.push_back(i - a);
f = S[f];
}
}
}
fout << rsp.size() << "\n";
vector <int> :: iterator it;
for (it = rsp.begin(); it != rsp.end(); it++)
{
fout << *it << " ";
}
return 0;
}