Pagini recente » Cod sursa (job #41561) | Cod sursa (job #1888320) | Cod sursa (job #755442) | Cod sursa (job #2777278) | Cod sursa (job #2284729)
///cu indexare de la 0
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define NMAX 2000001
char pattern[NMAX], text[NMAX];
int pref[NMAX];
void make_prefix(char pattern[])
{
int k = -1;
pref[0] = -1;
for(int i = 1; pattern[i]; ++i) {
while(pattern[k+1] != pattern[i] && k != -1) k = pref[k];
if(pattern[k+1] == pattern[i]) ++k;
pref[i] = k;
}
}
int main()
{
fin>>pattern>>text;
make_prefix(pattern);
int k = -1;
int len_pattern = strlen(pattern);
vector<int> res;
for(int i = 0; text[i]; ++i) {
while(pattern[k+1] != text[i] && k != -1) k = pref[k];
if(pattern[k+1] == text[i]) ++k;
if(k+1 == len_pattern) res.push_back(i - len_pattern + 1), k = pref[k];
}
fout<<res.size()<<'\n';
k = min((int)res.size(), 1000);
for(int i = 0; i < k; ++i)
fout<<res[i]<<' ';
return 0;
}