Pagini recente » Cod sursa (job #1102578) | Cod sursa (job #1268595) | Cod sursa (job #1168254) | Cod sursa (job #1738888) | Cod sursa (job #2266775)
#include <bits/stdc++.h>
using namespace std;
char s[4000020];
int z[4000020];
int rez[1010];
int main()
{
ios_base::sync_with_stdio(false);
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin.getline(s, 4000020);
int n = fin.gcount() - 1, lrez = 0, m;
m = n;
s[n] = '#';
fin.getline(s + n + 1, 4000020);
n += fin.gcount() - 1;
int l = 0, r = 0;
for(int i = 1; i < n; i++) {
if(i <= r) {
z[i] = min(z[i - l], r - i + 1);
}
while(i + z[i] - 1 < n && s[i + z[i]] == s[z[i]]) {
z[i]++;
}
if(i + z[i] - 1 >= r) {
r = i + z[i] - 1;
l = i;
}
if(z[i] == m) {
lrez++;
if(lrez <= 1000)
rez[lrez] = i - m - 1;
}
}
fout << lrez << '\n';
for(int i = 1; i <= min(1000, lrez); i++)
fout << rez[i] << ' ';
return 0;
}