Pagini recente » Cod sursa (job #1951130) | Cod sursa (job #687764) | Cod sursa (job #1910868) | Cod sursa (job #1905056) | Cod sursa (job #854464)
Cod sursa(job #854464)
#include <fstream>
#include <string>
#include <vector>
#define mod1 666001
#define mod2 666013
using namespace std;
string A,B;
vector <int> I;
int cod1,cod2,h1,h2,k1=0;
int litere(char c)
{
int x=0;
if (c>='A' && c<='Z') x=c-'A';
else if (c>='a' && c<='z') x=c-'a'+26;
else x=c-'0' +52;
return x;
}
void solveA(int &cod1,int &cod2)
{
int c1=0,c2=0;
int s=A.size()-1;
for (int i=0;i<=s;i++)
{
c1=((c1*62)%mod1+litere(A[i]))%mod1;
c2=((c2*62)%mod2+litere(A[i]))%mod2;
}
cod1=c1;
cod2=c2;
}
void solveB()
{
int i,length=A.size()-1,k2=0;
int pow1=1,pow2=1;
for(i=0;i<=length;i++)
{
h1=((h1*62)%mod1+litere(B[i]))%mod1;
h2=((h1*62)%mod2+litere(B[i]))%mod2;
if (i) {pow1=(pow1*62)%mod1; pow2=(pow2*62)%mod2; }
}
if (cod1==h1 && cod2==h2)
{
k1++;
I.push_back(0);
}
int length2=B.size();
for(i=length+1;i<length2;i++)
{
h1=(h1-(litere(B[k2])*pow1)%mod1+mod1)%mod1;
h2=(h2-(litere(B[k2])*pow2)%mod2+mod2)%mod2;
h1=((h1*62)%mod1+litere(B[i]))%mod1;
h2=((h1*62)%mod2+litere(B[i]))%mod2;
k2++;
if (cod1==h1 && cod2==h2) {k1++;
if(k1<=1000) I.push_back(k2);}
}
}
int main()
{
ifstream in("strmatch.in");
ofstream out("strmatch.txt");
in>>A;
in>>B;
out<<A<<"\n";
out<<B<<"\n";
solveA(cod1,cod2);
solveB();
// printf("%d\n ",k1);
//for(int j=0;j<k1;j++)
// {printf("%d ",I[j]);}
out<<k1<<"\n";
for (int i=0;i<I.size();i++)
{
out<<I[i]<<" ";
}
return 0;
}