Pagini recente » Cod sursa (job #633235) | Cod sursa (job #2428863) | Cod sursa (job #1875427) | Cod sursa (job #2845302) | Cod sursa (job #2462029)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int MAXN = 4*1e6 + 5;
char t1[MAXN],t2[MAXN],t[MAXN];
int Z[MAXN];
int main() {
fin >> (t1 + 1) >> (t2 + 1);
int n = strlen(t1 + 1), m =strlen(t2 + 1),cnt = 0;
for ( int i = 1; i <= n; ++i)
t[++cnt] = t1[i];
t[++cnt] = '$';
for ( int i = 1; i <= m; ++i)
t[++cnt] = t2[i];
int index = 1,l = 0,r = 0,q;
Z[1] = 1;
q = strlen(t+1);
for ( int i = 2; i <= q; ++i)
if (i > r) {
r = l = i;
while(t[r] == t[r-l + 1] and r <= q)
++r;
--r;
Z[i] = r-l+1;
}
else {
int lung = r - i;
int poz = i - l;
if ( Z[poz] <= lung)
Z[i] = Z[poz];
else {
while ( t[r] == t[r-l+1] and r <= q)
++r;
--r;
Z[i] = r-l+1;
l = i;
}
}
cnt = 0;
for ( int i = n+1; i <= q; ++i)
if ( Z[i] == n)
++cnt;
fout << cnt << "\n";
for ( int i = n+1; i <= q; ++i)
if ( Z[i] == n)
fout << i - n-2 << " ";
}