Pagini recente » Cod sursa (job #73828) | Cod sursa (job #2856503) | Cod sursa (job #2674482) | Cod sursa (job #47869) | Cod sursa (job #2883492)
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int i, j;
vector <int> pi, out;
char a[2000002], b[2000002];
void prefix ()
{
int k = 0;
pi.resize(strlen(a)+1);
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 main()
{
fin >> (a+1) >> (b+1);
a[0] = ' ';
b[0] = ' ';
prefix();
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 && out.size() <= 1000)
out.push_back(i-strlen(a)+1);
}
fout << out.size() << "\n";
for (i = 0; i < min((int) out.size(), 1000); i++)
fout << out[i] << " ";
return 0;
}