Pagini recente » Cod sursa (job #1841205) | Cod sursa (job #2965608) | Cod sursa (job #389160) | Cod sursa (job #748499) | Cod sursa (job #1316709)
#include<fstream>
#include<vector>
#include<cstring>
#define MAXN 2000002
#define SOLSIZE 1000
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char c, WORD[MAXN];
int PI[MAXN+1], wordlen;
#define PI (PI+1)
void process() {
fin>>WORD[0];
PI[0] = -1;
int i, cnd = 0;
for(i=0; WORD[i++] != '\n';) {
fin>>noskipws>>WORD[i];
while(cnd != -1 && WORD[i] != WORD[cnd]) cnd = PI[cnd];
if(cnd == -1) {
cnd = 0;
PI[i] = 0;
} else {
cnd++;
PI[i] = cnd;
}
}
WORD[i] = 0;
wordlen = i-1;
}
vector<int> SOL;
int ap;
void search() {
int stare = 0;
for(int i=0; fin>>noskipws>>c, c != '\n';i++) {
while(c != WORD[stare] && stare != -1) {
stare = PI[stare];
}
if(stare == -1) {
stare = 0;
} else {
stare ++;
if(stare == wordlen) {
ap++;
if(SOL.size() <= SOLSIZE)
SOL.push_back(i);
stare = PI[stare-1];
}
}
}
}
void afis() {
fout<<ap<<'\n';
for(vector<int>::iterator it=SOL.begin(); it!=SOL.end(); ++it) {
fout<<*it - wordlen + 1<<" ";
}
}
int main() {
process();
search();
afis();
return 0;
}