Pagini recente » Cod sursa (job #1408056) | Cod sursa (job #2035951) | Cod sursa (job #1242023) | Cod sursa (job #194579) | Cod sursa (job #2907751)
#include <fstream>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int mod = 1e9 + 7;
char v[2000000];
char v2[2000000];
int ans[1000],cnt = 0;
void ce(int a,int n){
if(a < 0)return;
int i = 0;
while(i < n && v[i] == v2[i + a]){
i++;
}
if(i == n){
if(cnt < 1000){
ans[cnt] = a;
}
cnt++;
}
}
int main()
{
int n = 0,i,m = 0,h = 0,h2 = 0,p = 1;
v[n++] = fin.get();
while(v[n - 1] != '\n'){
v[n++] = fin.get();
};
n--;
v2[m++] = fin.get();
while(v2[m - 1] != '\n'){
v2[m++] = fin.get();
};
m--;
for(i = 0;i < n;i++){
h = (1ll*h*26 + v[i] - 'A')%mod;
h2 = (1ll*h2*26 + v2[i] - 'A')%mod;
p = 1ll*p*26%mod;
}
for(i = n;i < m;i++){
///check equality
if(h == h2){
ce(i - n,n);
}
///add v2[i]
h2 = (1ll*h2*26 + v2[i] - 'A')%mod;
///remove v2[i - n]
h2 = (0ll + h2 - 1ll*(v2[i - n] - 'A')*p)%mod;
if(h2 < 0)h2+=mod;
}
if(h == h2 && i - n >= 0){
ce(i - n,n);
}
fout<<cnt<<'\n';
for(i = 0;i < min(cnt,1000);i++){
fout<<ans[i]<<' ';
}
return 0;
}