Pagini recente » Cod sursa (job #1105763) | Cod sursa (job #1433979) | Cod sursa (job #1737052) | Cod sursa (job #1843531) | Cod sursa (job #1383624)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int maxn = 2000005;
int n, m, z[maxn * 2];
string a, b, text;
inline int expand(int i, int j) {
int cnt = 0;
for(cnt = 0 ; j + cnt < text.size() ; ++ cnt)
if(text[i + cnt] != text[j + cnt])
return cnt;
return cnt;
}
inline void zalg() {
int l = -1, r = -1;
for(int i = 1 ; i < text.size() ; ++ i) {
if(i > r) {
z[i] = expand(0, i);
if(z[i]) {
l = i - z[i] + 1;
r = i;
}
}
else {
int lasti = r - i;
if(z[lasti] < r - i + 1)
z[i] = z[lasti];
else {
z[i] = r - i + 1 + expand(r - l + 1, r + 1);
if(i + z[i] > r) {
r = i + z[i];
l = i;
}
}
}
}
vector <int> matches;
for(auto i = a.size() ; i < text.size() ; ++ i)
if(z[i] >= a.size())
matches.push_back(i - a.size());
fout << matches.size() << '\n';
for(auto it : matches)
fout << it << ' ';
}
int main() {
getline(fin, a);
getline(fin, b);
text = a + b;
zalg();
}