Pagini recente » Cod sursa (job #2603408) | Cod sursa (job #2579671) | Cod sursa (job #2257225) | Cod sursa (job #3244520) | Cod sursa (job #715301)
Cod sursa(job #715301)
#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;
//
int nSubsir = sSir-sCuv+1; static unsigned int subsir_h[_SIZEM];
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> v;
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)) v.push_back(i);
}
//write
printf("%d\n", v.size());
for (int i=0; i<v.size() && i<1000 ;i++)
printf("%d ", v.at(i));
return 0;
}