Pagini recente » Cod sursa (job #848477) | Cod sursa (job #1359996) | Cod sursa (job #251884) | Cod sursa (job #1433786) | Cod sursa (job #3257357)
#include<fstream>
#include<cstring>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
char A[2000000],B[2000000];
int fv[90],n,m,i,d,nr_apar,sol[2000000],sol_ind;
int valid(int a,int b)
{
for(int i2=0;i2<m;i2++)
if(A[a+i2]!=B[b+i2])
return 0;
sol_ind++;
sol[sol_ind]=b;
return 1;
}
int main()
{
cin>>A>>B;
n=strlen(B);
m=strlen(A);
for(i=0;i<n;i++)
{
if(B[i]<='9' && B[i]>='0')
fv[B[i]-'0']=1;
if(B[i]>='A' && B[i]<='Z')
fv[B[i]-'A'+10]=1;
if(B[i]>='a' && B[i]<='z')
fv[B[i]-'a'+36]=1;
}
for(int j=0;j<62;j++)
if(fv[j])
d++;
int dput=1;///d^m-1
for(int z=1;z<m;z++)
dput*=d;
///calculare pattern A
int pa=0;
for(i=0;i<m;i++)
{
int putere=1;
if(A[i]>='0' && A[i]<='9')
{
for(int j2=1;j2<=i;j2++)
putere*=d;
pa=pa+(A[i]-'0')*putere;
}
if(A[i]>='A' && A[i]<='Z')
{
for(int j2=1;j2<=i;j2++)
putere*=d;
pa=pa+(A[i]-'A')*putere;
}
if(A[i]>='a' && A[i]<='z')
{
for(int j2=1;j2<=i;j2++)
putere*=d;
pa=pa+(A[i]-'a')*putere;
}
}
///calculam primul pattern de la B
int pb=0;
for(i=0;i<m;i++)
{
int putere=1;
if(B[i]>='0' && B[i]<='9')
{
for(int j2=1;j2<=i;j2++)
putere*=d;
pb=pb+(B[i]-'0')*putere;
}
if(B[i]>='A' && B[i]<='Z')
{
for(int j2=1;j2<=i;j2++)
putere*=d;
pb=pb+(B[i]-'A')*putere;
}
if(B[i]>='a' && B[i]<='z')
{
for(int j2=1;j2<=i;j2++)
putere*=d;
pb=pb+(B[i]-'a')*putere;
}
}
if(pa==pb)
if(valid(0,0))
nr_apar++;
///rolling pattern
for(i=1;i<=n-m;i++)
{
int x,y;///T[K] si T[k+m]
if(B[i-1]>='0' && B[i-1]<='9')
x=B[i-1]-'0';
if(B[i-1]>='A' && B[i-1]<='Z')
x=B[i-1]-'A';
if(B[i-1]>='a' && B[i-1]<='z')
x=B[i-1]-'a';
if(B[i-1+m]>='0' && B[i-1+m]<='9')
y=B[i-1+m]-'0';
if(B[i-1+m]>='A' && B[i-1+m]<='Z')
y=B[i-1+m]-'A';
if(B[i-1+m]>='a' && B[i-1+m]<='z')
y=B[i-1+m]-'a';
pb=(pb-x)/d+y*dput;
if(pa==pb)
if(valid(0,i))
nr_apar++;
}
cout<<nr_apar<<endl;
for(i=1;i<=sol_ind;i++)
cout<<sol[i]<<' ';
return 0;
}