Pagini recente » Cod sursa (job #812489) | Cod sursa (job #450939) | Cod sursa (job #715442) | Cod sursa (job #2786853) | Cod sursa (job #715371)
Cod sursa(job #715371)
#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
int nFinds=0; vector<int> vFinds; vFinds.reserve(1000);
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))
{
nFinds++;
if (nFinds<=1000) vFinds.push_back(i);
}
}
//write
printf("%d\n", nFinds);
for (int i=0; i<vFinds.size() ;i++)
printf("%d ", vFinds[i]);
return 0;
}