Pagini recente » Cod sursa (job #2444135) | Cod sursa (job #3273186) | Cod sursa (job #1893560) | Cod sursa (job #1962208) | Cod sursa (job #1513795)
#include <fstream>
#include <string.h>
#define NMax 5000100
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int strl, patl, Z[NMax], sol[5010], k, l, r, conclen;
char conc[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>>(conc);
patl = strlen(conc);
conc[strlen(conc)] = '?';
f>>(conc+strlen(conc));
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;
}