Pagini recente » Cod sursa (job #575178) | Cod sursa (job #1722481) | Cod sursa (job #1100137) | Cod sursa (job #2625230) | Cod sursa (job #1496111)
#include <iostream>
#include <vector>
#include <fstream>
#include <cstdio>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
#define mm 2000005
int v[mm];
char rad[mm],sur[mm];
int sol[1001];
int main()
{
f >> rad >> sur;
int rad_size = strlen(rad);
int sur_size = strlen(sur);
for(int i = rad_size; i >= 1; i--) rad[i] = rad[i-1];
for(int i = sur_size; i >= 1; i--) sur[i] = sur[i-1];
v[1] = 0;
for(int i = 2; i <= rad_size; i++)
{
int j = v[i-1];
while(j and rad[i] != rad[j+1])
j = v[j];
if (rad[i] == rad[j+1])
v[i] = j+1;
else
v[i] = 0;
}
int p = 0;
for(int i = 1, j = 0; i <= sur_size; i++)
{
while(j and sur[i] != rad[j+1])
j = v[j];
if (sur[i] == rad[j+1])
j++;
if (j == rad_size)
{
if (p < 1000)
{
p++;
sol[p] = i - rad_size;
}
else
p++;
}
}
g<<p<<'\n';
for(int i = 1; i <= min(p,1000); i++)
g<<sol[i]<<" ";
return 0;
}