Pagini recente » Cod sursa (job #406260) | Cod sursa (job #170065) | Cod sursa (job #3255653) | Cod sursa (job #429110) | Cod sursa (job #1513783)
#include <fstream>
#include <string.h>
#define NMax 2010
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int strl, patl, Z[NMax], sol[1010], k, l, r, conclen;
char str[NMax], pattern[NMax], conc[2 * NMax];
void preprocess()
{
Z[0] = conclen;
int l = 0, r = 0;
for (int i = 1; i <= conclen; i++) {
if (i > r) {
r = l = i;
while (conc[r] == conc[r-l])
r++;
Z[i] = r - l;
r--;
}
else {
if (Z[i-l] < r-i+1)
Z[i] = Z[i-l];
else {
l = i;
while (conc[r] == conc[r - l])
r++;
Z[i] = r - l;
r--;
}
}
}
}
int main()
{
f>>(pattern)>>(str);
strl = strlen(str);
patl = strlen(pattern);
strcat(conc, pattern);
strcat(conc, "?");
strcat(conc, str);
conclen = strlen(conc);
preprocess();
for (int i = 0; i < conclen; i++) {
if (i > patl && Z[i] == patl) {
sol[0]++;
if (sol[0] <= 1000)
sol[sol[0]] = i - patl - 1;
}
}
g<<sol[0]<<"\n";
for (int i=1; i<=sol[0] && i<=1000; i++)
g<<sol[i]<<" ";
return 0;
}