Pagini recente » Cod sursa (job #2828673) | Cod sursa (job #2463643) | Cod sursa (job #1017753) | Cod sursa (job #2579074) | Cod sursa (job #2086115)
#include <fstream>
#include <cstring>
#define max_dim 2000010
using namespace std;
int nxt[max_dim], positions[1010];
char P[max_dim], T[max_dim];
int n, m, i, q, k;
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f >> P + 1;
n = strlen(P + 1);
f >> T + 1;
m = strlen(T + 1);
q = 0;
nxt[1] = 0;
for (i = 2; i <= m; i++)
{
while (P[i] != P[q+1] && q != 0)
q = nxt[q];
if(P[i] == P[q+1])
++q;
nxt[i] = q;
}
q=0;
for (i = 1; i <= n; i++)
{
while (T[i] != P[q+1] && q != 0)
q = nxt[q];
if (T[i] == P[q+1])
q++;
if(q == m)
{
k++;
if(k <= 1000) {
positions[k] = i - m;
}
q = nxt[q];
}
}
g << k <<"\n";
if(k > 1000) {
k = 1000;
}
for (i = 1; i <= k; i++)
g << positions[i] << " ";
return 0;
}