Pagini recente » Cod sursa (job #2625076) | Cod sursa (job #2294743) | Cod sursa (job #312943) | Cod sursa (job #2056104) | Cod sursa (job #2266748)
#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 + 1, 4000020);
int n = fin.gcount() - 1, lrez = 0, m;
m = n;
s[n + 1] = 1;
fin.getline(s + n + 2, 4000020);
n += fin.gcount() - 1;
int l = 0, r = 0;
for(int i = 2; 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] + 1]) {
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 - 2;
}
}
fout << lrez << '\n';
for(int i = 1; i <= min(1000, lrez); i++)
fout << rez[i] << ' ';
return 0;
}