Pagini recente » Cod sursa (job #1725218) | Cod sursa (job #2129008) | Cod sursa (job #1644784) | Cod sursa (job #753847) | Cod sursa (job #923879)
Cod sursa(job #923879)
#include <fstream>
#include <vector>
#include <string>
using namespace std;
void getKMPTable(vector<int> &T, const string &A){
T[0]=-1; T[1]=0;
unsigned pos=2, currl=0;
while(pos<A.size()){
if(A[pos-1]==A[currl]){ currl++; T[pos]=currl; pos++; }
else if(currl>0) currl=T[currl];
else{ T[pos]=0; pos++; }
}
}
int main(){
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string A,B; fin>>A>>B;
unsigned N=0;
vector<int> out(1000);
vector<int> table(A.size());
getKMPTable(table,A);
unsigned m=0,i=0;
while(m+i<B.size()){
if(B[m+i]==A[i]){
if(i==A.size()-1){
if(N<1000) out[N]=m; ++N;
m+=i-table[i]; i=table[i];
}
else ++i;
}
else{
m+=i-table[i];
if(table[i]<0) i=0;
else i=table[i];
}
}
fout<<N<<'\n';
if(N>1000) N=1000;
for(unsigned i=0;i<N;++i) fout<<out[i]<<' ';
fout<<'\n';
}