Pagini recente » Cod sursa (job #2654253) | Cod sursa (job #25341) | Cod sursa (job #945344) | Cod sursa (job #916461) | Cod sursa (job #2226007)
#include <bits/stdc++.h>
#define MAX 4000000
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[MAX], b[MAX];
int hashTableA[MAX], hashTableB[MAX];
queue < int > q;
bool isIndeed(int idx, int l)
{
int hA=0, i=idx+l-1;
while(idx<=i)
{
int sum = hashTableB[i]-hashTableB[idx-1];
int sum2 = hashTableA[l]-hashTableA[hA];
hA++;
idx++;
if(sum!=sum2)
return false;
}
return true;
}
int main()
{
f>>(a+1)>>(b+1);
int la=strlen(a+1);
int lb=strlen(b+1);
for(int i=1; i<=la; i++)
{
hashTableA[i]=hashTableA[i-1]+int(a[i]);
//cout<<hashTableA[i]<<" ";
}
//cout<<'\n';
for(int i=1; i<=lb; i++)
{
hashTableB[i]=hashTableB[i-1]+int(b[i]);
//cout<<hashTableB[i]<<" ";
}
//cout<<'\n';
for(int i=1; i<=lb-la+1; i++)
{
int sum = hashTableB[i+la-1]-hashTableB[i-1];
if(sum==hashTableA[la])
{
//cout<<"YES "<<i<<endl;
if(isIndeed(i, la))
q.push(i);
}
}
g<<q.size()<<'\n';
while(!q.empty())
{
int x = q.front();
g<<x-1<<" ";
q.pop();
}
}