Pagini recente » Cod sursa (job #2879189) | Cod sursa (job #232826) | Cod sursa (job #2195997) | Cod sursa (job #2955424) | Cod sursa (job #1875798)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int NMax = 2000000 + 3;
int nrSol;
int T[NMax],sol[NMax];
char patt[NMax],str[NMax];
int main() {
in.getline(patt+1,NMax - 3);
in.getline(str+1,NMax - 3);
int lenPatt = strlen(patt+1);
int lenStr = strlen(str+1);
if (lenPatt>lenStr) {
out<<0;
return 0;
}
for (int c=2;c<=lenPatt;++c) {
int nr = 0;
for (int i=1;i<=lenPatt-c+1;++i) {
if (patt[c+i-1]!=patt[i]) {
break;
}
nr++;
}
int i = c + nr - 1;
while (nr) {
T[i] = max(T[i],nr);
--nr;
--i;
}
}
int m=1;
int i=0;
while (m<=lenStr) {
if (str[m]==patt[i+1]) {
++i;
if (i==lenPatt) {
sol[++nrSol] = m-lenPatt+1;
i=T[i];
}
++m;
}
else {
if (i!=0) {
i=T[i];
}
else {
++m;
}
}
}
out<<nrSol<<'\n';
for (int i=1;i<=nrSol;++i) {
out<<sol[i]-1<<' ';
}
in.close();out.close();
return 0;
}