Pagini recente » Cod sursa (job #1140761) | Cod sursa (job #2513066) | Cod sursa (job #2487681) | Cod sursa (job #2119697) | Cod sursa (job #2974218)
#include <fstream>
#include <cstring>
#define MOD1 100021 ///1000000009
#define MOD2 100007 ///1000000007
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
char v[2000001];
int s[1001];
int main()
{
bool pp=true;
int n=1,m;
long long nr1=0,nr2=0,ns1=0,ns2=0;
long long p1=1,p2=1;
int sol=0;
char ch;
///0-9 => 0-9
///a-z => 10-35
///A-Z => 36-61
cin.get(ch);
if('0'<=ch && ch<='9')
{
nr1+=ch-'0';
nr2+=ch-'0';
}
else if('a'<=ch && ch<='z')
{
nr1+=ch-'a'+10;
nr2+=ch-'a'+10;
}
else if('A'<=ch && ch<='Z')
{
nr1+=ch-'A'+36;
nr2+=ch-'A'+36;
}
while(pp==true)
{
cin.get(ch);
if(ch=='\n')
pp=false;
else
{
n++;
p1*=62;
p2*=62;
p1=p1%MOD1;
p2=p2%MOD2;
if('0'<=ch && ch<='9')
{
nr1+=p1*(ch-'0');
nr1%=MOD1;
nr2+=p2*(ch-'0');
nr2%=MOD2;
}
else if('a'<=ch && ch<='z')
{
nr1+=p1*(ch-'a'+10);
nr1%=MOD1;
nr2+=p2*(ch-'a'+10);
nr2%=MOD2;
}
else if('A'<=ch && ch<='Z')
{
nr1+=p1*(ch-'A'+36);
nr1%=MOD1;
nr2+=p2*(ch-'A'+36);
nr2%=MOD2;
}
}
}
cin.getline(v,2000001);
m=strlen(v);
if(n>m)
cout<<0;
else
{
int i=1;
ch=v[n];
p1=1;
p2=1;
if('0'<=ch && ch<='9')
{
ns1+=ch-'0';
ns2+=ch-'0';
}
else if('a'<=ch && ch<='z')
{
ns1+=ch-'a'+10;
ns2+=ch-'a'+10;
}
else if('A'<=ch && ch<='Z')
{
ns1+=ch-'A'+36;
ns2+=ch-'A'+36;
}
for(i=n-1;i>=1;i--)
{
ch=v[i];
p1*=62;
p2*=62;
p1=p1%MOD1;
p2=p2%MOD2;
if('0'<=ch && ch<='9')
{
ns1+=p1*(ch-'0');
ns1%=MOD1;
ns2+=p2*(ch-'0');
ns2%=MOD2;
}
else if('a'<=ch && ch<='z')
{
ns1+=p1*(ch-'a'+10);
ns1%=MOD1;
ns2+=p2*(ch-'a'+10);
ns2%=MOD2;
}
else if('A'<=ch && ch<='Z')
{
ns1+=p1*(ch-'A'+36);
ns1%=MOD1;
ns2+=p2*(ch-'A'+36);
ns2%=MOD2;
}
}
for(i=n+1;i<=m;i++)
{
if(nr1==ns1 && nr2==ns2)
{
sol++;
if(sol<=1000)
s[sol]=i-n;
}
ch=v[i-n];
if('0'<=ch && ch<='9')
ch=ch-'0';
else if('a'<=ch && ch<='z')
ch=ch-'a'+10;
else if('A'<=ch && ch<='Z')
ch=ch-'A'+36;
ns1=ns1-1LL*(p1*ch)%MOD1+MOD1;
ns2=ns2-1LL*(p2*ch)%MOD2+MOD2;
ns1*=62;
ns2*=62;
ch=v[i];
if('0'<=ch && ch<='9')
ch=ch-'0';
else if('a'<=ch && ch<='z')
ch=ch-'a'+10;
else if('A'<=ch && ch<='Z')
ch=ch-'A'+36;
ns1+=ch;
ns2+=ch;
ns1%=MOD1;
ns2%=MOD2;
}
if(nr1==ns1 && nr2==ns2)
{
sol++;
if(sol<=1000)
s[sol]=i-n;
}
cout<<sol<<'\n';
for(i=1;i<=sol && i<=1000;i++)
cout<<s[i]<<" ";
}
return 0;
}