Pagini recente » Cod sursa (job #393799) | Cod sursa (job #2568584) | Cod sursa (job #2243802) | Cod sursa (job #226217) | Cod sursa (job #975841)
Cod sursa(job #975841)
#include<fstream>
#include<string>
#define MAXL 2000002
#define MOD 666013
#define BASE 101
using namespace std;
int pow[MAXL],l1,l2,sol[1001],nrsol,val1,val2;
string s1,s2;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
void citire()
{
fin>>s1>>s2;
l1=s1.length();
l2=s2.length();
}
void puteri()
{
pow[0]=1;
for(int i=1;i<=l1;i++)
{
pow[i]=(pow[i-1]*BASE)%MOD;
}
}
int transforma(string s,int l)
{
int p=0;
for(int i=0;i<=l;i++)
{
p=((s[i]*pow[l-i])%MOD+p)%MOD;
}
return p;
}
void adauga(int poz,int &val)
{
val-=(pow[l1-1]*s2[poz-l1])%MOD;
val=(val+MOD)%MOD;
val=((val*BASE)%MOD+s2[poz])%MOD;
}
void rezolva()
{
val1=transforma(s1,l1-1);
val2=transforma(s2,l1-1);
for(int i=l1;i<l2;i++)
{
if(val1==val2)
{
sol[++nrsol]=i-1;
if(nrsol==1000)
return;
}
adauga(i,val2);
}
if(val1==val2)
sol[++nrsol]=l2-1;
}
void afisare()
{
fout<<nrsol<<'\n';
for(int i=1;i<=nrsol;i++)
{
fout<<sol[i]-l1+1<<' ';
}
}
int main()
{
citire();
if(l1>l2)
{
fout<<0;
return 0;
}
puteri();
rezolva();
afisare();
return 0;
}