Pagini recente » Cod sursa (job #977709) | Cod sursa (job #2262978) | Cod sursa (job #2433654) | Cod sursa (job #2334577) | Cod sursa (job #2207273)
#include <fstream>
#include <string.h>
using namespace std;
char a[2000005], b[2000005];
int af[2000005];
int has, hbs, c=0, p=1;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
bool ok(int i)
{
if(i==strlen(a)-strlen(b)) return 0;
for(int j=0; j<strlen(b); j++)
if(b[j]!=a[i+j]) return 0;
return 1;
}
int main()
{
f>>b;
f>>a;
if(strlen(b)>strlen(a)) {g<<"0"; return 0;}
for(int i=0; i<strlen(b); i++)
{hbs=((hbs*73)+b[i])%100007;
has=((has*73)+a[i])%100007;
if(i) p=(p*73);
if(i!=(strlen(b)-1)) p=p%100007;}
for(int i=0; i<=strlen(a)-strlen(b); i++)
{
if(has==hbs)
if(ok(i))
{c++; af[c]=i;}
has=((has+100007-((a[i]*(p))%100007))*73+a[i+strlen(b)])%100007;
}
g<<c<<'\n';
for(int i=1; i<=c; i++) g<<af[i]<<" ";
return 0;
}