Pagini recente » Cod sursa (job #450952) | Cod sursa (job #643204) | Cod sursa (job #316353) | Cod sursa (job #877310) | Cod sursa (job #715310)
Cod sursa(job #715310)
#include<cstdio>
#include<cstring>
#include<vector>
const int _SIZEM = 2000010;
const int _BASE = 1<<31;
using namespace std;
int main()
{
//read
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
static char sir[_SIZEM], cuv[_SIZEM];
gets(cuv); gets(sir);
int sSir = strlen(sir), sCuv = strlen(cuv);
//hashes
int cuv_h=0;
for (int i=0; i<sCuv; i++)
cuv_h = (cuv_h + cuv[i]) % _BASE;
static unsigned int subsir_h[_SIZEM];
int nSubsir = sSir-sCuv+1;
subsir_h[0]= 0;
for (int i=0; i<sCuv; i++)
subsir_h[0] = (subsir_h[0] + sir[i]) % _BASE;
for (int i=1; i<=nSubsir; i++)
subsir_h[i] = (subsir_h[i-1] - sir[i-1] + sir[i+sCuv-1]) % _BASE;
//comparison
vector<int> vFinds; vFinds.reserve(100000);
for (int i=0; i<=nSubsir; i++)
if (subsir_h[i]==cuv_h)
{
int j;
for (j=0; sir[i+j]!=0 && cuv[j]!=0 && sir[i+j]==cuv[j] ;j++);
if (j==strlen(cuv)) vFinds.push_back(i);
}
//write
printf("%d\n", vFinds.size());
for (int i=0; i<vFinds.size() && i<1000 ;i++)
printf("%d ", vFinds[i]);
return 0;
}