Pagini recente » Cod sursa (job #967708) | Cod sursa (job #897692) | Cod sursa (job #1097371) | Cod sursa (job #571679) | Cod sursa (job #1168573)
#include<fstream>
#include<string>
using namespace std;
string text, pattern;
int esec[2000005], i, nrsol, sol[1005];
void makeprefix(){
esec[0]=-1;
for (int i=2; i<pattern.length(); ++i) {
int k=i-1;
while (k>0 && pattern[esec[k]+1]!=pattern[i]) k=esec[k];
esec[i]=esec[k]+1;
}
}
int main(void) {
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
getline(fin,pattern); pattern=' '+pattern;
getline(fin,text); text=' '+text;
makeprefix();
int k=0;
for (i=1; i<text.length(); ++i) {
while (k>0&&text[i]!=pattern[k+1]) k=esec[k];
++k;
if (k==pattern.length()-1) {
++nrsol;
if (nrsol<=1000) sol[nrsol]=i-(pattern.length()-1);
k=esec[k];
}
}
fout<<nrsol<<"\n";
for (i=1; i<=min(nrsol,1000); ++i) fout<<sol[i]<<" ";
return 0;
}