Pagini recente » Cod sursa (job #1850002) | Cod sursa (job #126137) | Cod sursa (job #311602) | Cod sursa (job #1789046) | Cod sursa (job #908011)
Cod sursa(job #908011)
#include <fstream>
#include <cstring>
#define N 4000010
using namespace std;
int i, j, n, m, L, R, k, Z[N];
string A, B;
int main()
{
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
fi >> A >> B;
m = A.length();
A = A + "#" + B + "#";
n = A.length(); n--;
L = R = 0;
for(i = 1; i < n; i++)
if(R <= i)
{
L = R = i;
while(R < n and A[R] == A[R-i]) R++;
Z[i] = R - i; R--;
} else
{
j = i - L;
if(Z[j] < R - i + 1)
{
Z[i] = Z[j];
continue;
}
L = i;
while(R < n and A[R] == A[R-i]) R++;
Z[i] = R - i; R--;
}
for(i = 1; i < n; i++) if(Z[i] == m) k++;
fo << k << "\n";
for(i = 1, k = 0; i < n and k < 1000; i++) if(Z[i] == m) fo << i - m - 1 << " ", k++;
return 0;
}