Pagini recente » 0931011001 | Istoria paginii runda/oji_2006_10/clasament | Cod sursa (job #954116) | Cod sursa (job #26194) | Cod sursa (job #2789457)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int rasp[1001];
string a,b;
void subsir()
{
int nr=0;
int n=a.size();
long long pp,c=0,cod=0,p=1;
long long mod=100007;
for(int i=n-1; i>=0; i--)
{
cod+=(a[i]-'A')*p;
cod%=mod;
p*=26;
p%=mod;
if(i==1)pp=p;
}
int m=b.size();
p=1;
for(int i=n-1; i>=0; i--)
{
c+=(b[i]-'A')*p;
cod%=mod;
p*=26;
p%=mod;
}
if(c==cod)
{
int i=0;
while(a[i]==b[i]&&i<n)
{
i++;
}
if(i==n)
{
rasp[++nr]=0;
}
}
for(int i=n; i<m; i++)
{
c-=(b[i-n]-'A')*pp;
c*=26;
c%=mod;
c+=b[i]-'A';
c%=mod;
if(c==cod)
{
int j=0;
int k=i-n+1;
while(a[j]==b[k]&&j<n)
{
j++;
k++;
}
if(j==n)
{
rasp[++nr]=i-n+1;
if(nr==1000)break;
}
}
}
fout<<nr<<'\n';
for(int i=1; i<=nr; i++)fout<<rasp[i]<<" ";
}
int main()
{
fin>>a;
fin.get();
fin>>b;
subsir();
return 0;
}