Pagini recente » Cod sursa (job #426296) | Cod sursa (job #812538) | Cod sursa (job #1018469) | Cod sursa (job #393030) | Cod sursa (job #3247103)
#include <fstream>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int Z[4000005];
string A,B,concat;
void buildZ()
{
int nrMatches=0;
concat=A+"*"+B;
int st=0,dr=0;
for(int i=1;i<concat.length();++i){
if(i>dr){
st=i;
dr=i;
while(concat[dr]==concat[dr-st]&&dr<concat.length()){
dr++;
}
Z[i]=dr-st;
dr--;
}
else{
int k=i-st;
if(Z[k]<dr-i+1){
Z[i]=Z[k];
}
else{
st=i;
while(dr<concat.length() && concat[dr]==concat[dr-st]){
dr++;
}
Z[i]=dr-st;
dr--;
}
}
if(Z[i]==A.length()){
nrMatches++;
}
}
fout << nrMatches << '\n';
}
void findMatches()
{
int cnt=0;
for(int i=1;i<concat.length();++i){
if(Z[i]==A.length()){
cnt++;
if(cnt<=1000){
fout << i-A.length()-1 << ' ';
}
else{
break;
}
}
}
}
int main()
{
fin >> A >> B;
buildZ();
findMatches();
return 0;
}