Pagini recente » Cod sursa (job #347410) | Cod sursa (job #650782) | Cod sursa (job #310509) | Cod sursa (job #1161265) | Cod sursa (job #1316682)
#include<fstream>
#include<vector>
#include<cstring>
#define MAXN 2000001
#define SOLSIZE 1000
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char STRING[MAXN], WORD[MAXN];
int PI[MAXN+1], wordlen;
#define PI (PI+1)
void process() {
wordlen = strlen(WORD);
for(int i=1; WORD[i]; ++i) {
if(WORD[i] == WORD[PI[i-1]])
PI[i] = PI[i-1] + 1;
else PI[i] = 0;
}
}
vector<int> SOL;
int ap;
void search() {
int stare = 0;
int len = strlen(STRING);
for(int i=0; i<len; i++) {
if(STRING[i] == WORD[stare]) {
stare++;
if(stare == strlen(WORD)) {
ap++;
if(SOL.size() <= SOLSIZE)
SOL.push_back(i);
stare = PI[stare-1];
}
} else {
stare = PI[stare];
}
}
}
void afis() {
fout<<ap<<'\n';
for(vector<int>::iterator it=SOL.begin(); it!=SOL.end(); ++it) {
fout<<*it - wordlen + 1<<" ";
}
}
int main() {
fin>>WORD>>STRING;
process();
search();
afis();
return 0;
}