Pagini recente » Cod sursa (job #2404308) | Cod sursa (job #1359587) | Cod sursa (job #3033039) | Cod sursa (job #1349109) | Cod sursa (job #2938617)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string s1,s2;
unsigned long long h1, h2, p_n=1;
long long p=31;
vector <int> prez;
int main()
{
/*r=strstr(s2, s1);
if(r)
v[++nr]=r-s2;
v[0]=0;
while(r){
strcpy(aux, r+1);
r=strstr(aux, s1);
if(r)
nr++, v[nr]=r-aux+v[nr-1]+1;
}
cout<<nr<<'\n';
for(int i=1; i<=nr; i++)
cout<<v[i]<<' ';*/
///
/*for(int i=1; i<strlen(s2)-strlen(s1); i++){
bool ok=true;
for(int j=0; j<strlen(s1) and ok; j++)
if(s1[j]!=s2[i+j]) ok=false;
if(ok) v[++nr]=i;
}
cout<<nr<<'\n';
for(int i=1; i<=nr; i++)
cout<<v[i]<<' ';*/
///
fin>>s1>>s2;
if(s1.size()> s2.size()) swap(s1, s2);
for(int i=0; i<s1.size(); i++){
h1=h1*p+s1[i];
h2=h2*p+s2[i];
p_n=p_n*p;
}
if(h1==h2)
prez.push_back(0);
for(int i=s1.size(); i<s2.size(); i++){
h2=h2*p+s2[i]-p_n*s2[i-s1.size()];
if(h1==h2)
prez.push_back(i-s1.size()+1);
}
fout<<prez.size()<<'\n';
for(int i=0; i<min(1000, (int)prez.size()); i++)
fout<<prez[i]<<' ';
return 0;
}