Pagini recente » Cod sursa (job #657934) | Cod sursa (job #2163591) | Cod sursa (job #22337) | Cod sursa (job #495848) | Cod sursa (job #1747503)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 2e6 + 5;
string txt, pat, cat;
int z[NMAX];
int main(void) {
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n, m, k, l, r, ant;
ant = 0;
l = 0;
r = -1;
f>>pat>>txt;
cat = pat + "#" + txt;
for (int i=1; i<cat.size(); ++i) {
if (i>r) {
for(l=r=i; cat[r-l]==cat[r] && r<cat.size(); ++r);
z[i] = r - l;
--r;
}
else {
k = i - l;
if (z[k] < r-i+1) {
z[i] = z[k];
}
else {
l = i;
for(; r<cat.size() && cat[r-l]==cat[r]; ++r);
z[i] = r - l;
--r;
}
}
}
for(int i=pat.size(); i<cat.size(); ++i)
if(z[i]>=pat.size())
++ant;
ant = min(ant, 1000);
g<<ant<<'\n';
for(int i=pat.size(); ant && i<cat.size(); ++i)
if(z[i]>=pat.size())
g<<i-pat.size()-1<<' ';
g<<'\n';
f.close();
g.close();
return 0;
}