Pagini recente » Cod sursa (job #2406330) | Cod sursa (job #2097251) | Cod sursa (job #2162787) | Cod sursa (job #2603045) | Cod sursa (job #2129160)
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
ifstream input("strmatch.in");
ofstream output("strmatch.out");
#define minim(a, b) ((a < b) ? a : b)
#define MAX 2000005
string A, B;
int pi[MAX], pos[1024];
void make_prefix(int m)
{
int q = 0;
pi[1] = 0;
for (int i = 2; i <= m; i++)
{
while(q && A[q+1] != A[i])
q = pi[q];
if(A[q+1] == A[i])
q++;
pi[i] = q;
}
}
int main()
{
getline(input, A);
getline(input, B);
getline(input, B);
int m = A.size();
int n = B.size();
for (int i = m; i; --i) A[i] = A[i-1]; A[0] = ' ';
for (int i = n; i; --i) B[i] = B[i-1]; B[0] = ' ';
make_prefix(m);
int q = 0, p = 0;
for (int i = 1; i <= n; ++i)
{
while (q && A[q+1] != B[i])
q = pi[q];
if (A[q+1] == B[i])
++q;
if (q == m)
{
q = pi[m];
++p;
if (p <= 1000)
pos[p] = i-m;
}
}
output << p;
for (int i = 1; i <= minim(p, 1000); ++i)
output << pos[i] << " ";
return 0;
}