Pagini recente » Cod sursa (job #2425762) | Cod sursa (job #107569) | Cod sursa (job #2235285) | Cod sursa (job #3290945) | Cod sursa (job #2284725)
#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 = 0;
for(int i = 2; pattern[i]; ++i) {
while(pattern[k+1] != pattern[i] && k) k = pref[k];
if(pattern[k+1] == pattern[i]) ++k;
pref[i] = k;
}
}
int main()
{
fin>>(pattern+1)>>(text+1);
make_prefix(pattern);
int k = 0;
int len_pattern = strlen(pattern+1);
vector<int> res;
for(int i = 1; text[i]; ++i) {
while(pattern[k+1] != text[i] && k) k = pref[k];
if(pattern[k+1] == text[i]) ++k;
if(k == len_pattern) res.push_back(i - len_pattern), 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;
}