Pagini recente » Cod sursa (job #2051976) | Cod sursa (job #3264734) | Cod sursa (job #1000346) | Cod sursa (job #2452308) | Cod sursa (job #999686)
Cod sursa(job #999686)
#include<fstream>
#include<string>
#include<cmath>
using namespace std;
#define dimMAX 2000002;
#define P 73
#define MOD1 100007
#define MOD2 100021
int match[2000002];
int p1,p2;
int main(){
string A,B;
ifstream inFile("strmatch.in");
getline(inFile,A);
getline(inFile,B);
int a,b;
a=A.size()-1;
b=B.size()-1;
ofstream outFile;
outFile.open("strmatch.out");
long long hashA=0;
long long hashB=0;
for(int i=0;i<=a;i++){
hashA=(hashA*P+A[i])%MOD1;
hashB=(hashB*P+B[i])%MOD1;
if(i!=0) p1=(p1*P)%MOD1;
}
int nr=0;
if(hashA==hashB){
nr++;
match[nr]=0;
}
/* for(int i=1;i<=b-a;i++){
hashB = ((hashB - (B[i-1] * p1) % MOD1 + MOD1) * P + B[i+a]) % MOD1;
if(hashB==hashA){
nr++;
match[nr]=i;
}
}
*/
for(int i=a+1;i<=b;i++){
hashB = ((hashB - (B[i - a+1] * p1) % MOD1 + MOD1) * P + B[i]) % MOD1;
if(hashB==hashA){
nr++;
match[nr]=i-a+1;
}
}
outFile<<nr<<"\n";
if(nr>1000) nr=1000;
for(int i=1;i<=nr;i++) outFile<<match[i]<<" ";
}