Pagini recente » Cod sursa (job #1341180) | Cod sursa (job #941121) | Cod sursa (job #1439071) | Cod sursa (job #3121038) | Cod sursa (job #1382474)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int maxn = 2000005;
string a, b, whole;
int z[maxn], n, m;
inline int extend(string a, int i, int j) {
int sum;
for(sum = 0 ; j + sum < a.size() ; ++ sum)
if(a[i + sum] != a[j + sum])
return sum;
return sum;
}
inline void buildz(string a) {
int l = -1, r = -1;
for(int i = 1 ; i < a.size() ; ++ i) {
if(i >= r) {
z[i] = extend(a, 0, i);
l = i;
r = i + z[i] - 1;
}
else {
int lasti = i - l;
if(z[lasti] <= r - l + 1)
z[i] = z[lasti];
else {
z[i] = z[lasti] + extend(a, lasti + z[lasti] - 1, i + z[lasti] - 1);
if(r < i + z[i] - 1) {
l = i;
r = i + z[i] - 1;
}
}
}
}
}
int main() {
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
getline(fin, a);
getline(fin, b);
int aux = a.size();
a += b;
buildz(a);
int ans = 0;
vector <int> matches;
for(int i = aux ; i < a.size() ; ++ i)
if(z[i] >= aux) {
++ ans;
if(ans <= 1000)
matches.push_back(i - aux);
}
fout << ans << '\n';
for(auto it : matches)
fout << it << ' ';
}