Pagini recente » Cod sursa (job #1950318) | Cod sursa (job #294570) | Cod sursa (job #1710761) | Cod sursa (job #317680) | Cod sursa (job #1148853)
#include <fstream>
#include <cstring>
#define mod1 123456
#define mod2 145678
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
char c[2000010],x[2000010];
long long n1,n2,putere1,putere2,nr1,nr2,nrc1,nrc2,i,nr;
bool f[2000010];
int main () {
fin>>c;
fin>>x;
n1=strlen (c);
n2=strlen (x);
if (c>x) {
fout<<"0\n";
return 0;
}
putere1=putere2=1;
for (i=0;i<n1;i++) {
nr1=(nr1*26 + c[i]-'A')%mod1;
nr2=(nr2*26 + c[i]-'A')%mod2;
if (i!=0) {
putere1=(putere1*26)%mod1;
putere2=(putere2*26)%mod2;
}
}
for (i=0;i<n1;i++) {
nrc1=(nrc1*26 + x[i]-'A')%mod1;
nrc2=(nrc2*26 + x[i]-'A')%mod2;
}
if (nrc1==nr1&&nrc2==nr2) {
f[0]=1;
nr++;
}
for (i=n1;i<n2;i++) {
nrc1=((nrc1-((x[i-n1]-'A')*putere1)%mod1+mod1)*26+(x[i]-'A'))%mod1;
nrc2=((nrc2-((x[i-n1]-'A')*putere2)%mod2+mod2)*26+(x[i]-'A'))%mod2;
if (nrc1==nr1&&nrc2==nr2) {
f[i-n1+1]=1;
nr++;
}
}
fout<<nr<<"\n";
if (nr>1000)
nr=1000;
for (i=0;nr;i++) {
if (f[i]==1) {
fout<<i<<" ";
nr--;
}
}
return 0;
}