Pagini recente » Cod sursa (job #1721175) | Cod sursa (job #1049102) | Cod sursa (job #449619) | Cod sursa (job #2352549) | Cod sursa (job #2211601)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
class OutParser {
private:
FILE *fout;
char *buff;
int sp;
void write_ch(char ch) {
if (sp == 50000) {
fwrite(buff, 1, 50000, fout);
sp = 0;
buff[sp++] = ch;
} else {
buff[sp++] = ch;
}
}
public:
OutParser(const char* name) {
fout = fopen(name, "w");
buff = new char[50000]();
sp = 0;
}
~OutParser() {
fwrite(buff, 1, sp, fout);
fclose(fout);
}
OutParser& operator << (int vu32) {
if (vu32 <= 9) {
write_ch(vu32 + '0');
} else {
(*this) << (vu32 / 10);
write_ch(vu32 % 10 + '0');
}
return *this;
}
OutParser& operator << (long long vu64) {
if (vu64 <= 9) {
write_ch(vu64 + '0');
} else {
(*this) << (vu64 / 10);
write_ch(vu64 % 10 + '0');
}
return *this;
}
OutParser& operator << (char ch) {
write_ch(ch);
return *this;
}
OutParser& operator << (const char *ch) {
while (*ch) {
write_ch(*ch);
++ch;
}
return *this;
}
};
OutParser fout("strmatch.out");
typedef long long ll;
const ll MOD=1000000007;
const int N=2000000;
const int BASE=62;
ll expow(ll a,ll b)
{
ll ans=1;
while(b>0)
{
if(b%2==1)
ans=(ll)ans*a%MOD;
a=(ll)a*a%MOD;
b/=2;
}
return ans;
}
char s[N+5];
int len1;
int len2;
ll inv,add;
ll f(char ch)
{
if('0'<=ch && ch<='9')
return ch-'0';
if('a'<=ch && ch<='z')
return ch-'a'+10;
return ch-'A'+36;
}
ll caut=0;
int cnt=0;
int sol[1005];
int main()
{
fin.getline(s,N+5);
len1=strlen(s);
inv=expow(62,MOD-2);
add=expow(62,len1-1);
ll cur=1;
for(int i=0;i<len1;i++)
{
caut=(caut+(ll)cur*f(s[i]))%MOD;
cur=(ll)cur*62%MOD;
}
fin.getline(s,N+5);
len2=strlen(s);
if(len2<len1)
{
fout<<"0\n";
return 0;
}
ll am=0;
cur=1;
for(int i=0;i<len1;i++)
{
am=(am+(ll)cur*f(s[i]))%MOD;
cur=(ll)cur*62%MOD;
}
if(am==caut)
{
sol[++cnt]=0;
}
for(int st=1;st+len1-1<len2;st++)
{
am-=f(s[st-1]);
if(am<0)
am+=MOD;
am=(ll)am*inv%MOD;
am=(am+(ll)add*f(s[st+len1-1]))%MOD;
if(am==caut)
{
if(cnt<1000)
sol[++cnt]=st;
else
cnt++;
}
}
fout<<cnt<<"\n";
for(int i=1;i<=min(cnt,1000);i++)
fout<<sol[i]<<" ";
fout<<"\n";
return 0;
}