Pagini recente » Cod sursa (job #2574496) | Cod sursa (job #2060160) | Cod sursa (job #2530698) | Cod sursa (job #1288926) | Cod sursa (job #3239628)
#include <fstream>
#include <vector>
#define f first
#define s second
const int NMAX=2e6+5;
const int B=31;
const int MOD1=1e9+7;
const int MOD2=666013;
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
char s[NMAX], t[NMAX];
pair<int, int> hsh[NMAX], hs, pw[NMAX];
vector <int> ans;
bool check(int i, int lg)
{
pair<int, int> val;
val.f=(hsh[i].f-(hsh[i-lg].f*pw[lg].f)%MOD1+MOD1)%MOD1;
val.s=(hsh[i].s-(hsh[i-lg].s*pw[lg].s)%MOD2+MOD2)%MOD2;
return (val==hs);
}
int main()
{
int i, lg=0;
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin>>s>>t;
pw[0]={1, 1};
for(i=1; s[i-1] || t[i-1]; i++)
{
pw[i].f=(pw[i-1].f*B)%MOD1;
pw[i].s=(pw[i-1].s*B)%MOD2;
}
for(i=0; s[i]; i++)
{
lg++;
hs.f=((hs.f*B)%MOD1+(s[i]-'A'+1))%MOD1;
hs.s=((hs.s*B)%MOD2+(s[i]-'A'+1))%MOD2;
}
hsh[0]={0, 0};
for(i=0; t[i]; i++)
{
hsh[i+1].f=((hsh[i].f*B)%MOD1+(t[i]-'A'+1))%MOD1;
hsh[i+1].s=((hsh[i].s*B)%MOD2+(t[i]-'A'+1))%MOD2;
if(i+1>=lg && check(i, lg)) ans.push_back(i-lg);
}
cout<<ans.size()<<'\n';
int cnt=0;
for(auto i:ans)
{
cnt++;
cout<<i<<' ';
if(cnt==1000) break;
}
return 0;
}