Pagini recente » Cod sursa (job #2797942) | Cod sursa (job #3259742) | Cod sursa (job #1084479) | Cod sursa (job #2552274) | Cod sursa (job #2721175)
#include <iostream>
#include <fstream>
#include <vector>
const int MAXN = 2e6 + 1;
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string a,b;
string s;
int z[MAXN];
void zalgorithm(){
int n = s.size();
int r = -1;
int l = -1;
for(int i = 1; i < n; i++){
if(i > r){
int k = 0;
while(i + k < n && s[i + k] == s[k]){
k++;
}
l = i;
r = i + k - 1;
z[i] = k;
}else{
if(s[i] != s[0]){
z[i] = 0;
}else{
int defazaj = i - l;
int initial = min(z[defazaj],r - i + 1);
int start = i + initial;
// defazaj++;
int k = 0;
// cout<<defazaj<<" "<<initial<<" "<<s[start]<<" "<<s[k + initial]<<endl;
while(start + k < n && s[start + k] == s[k + initial])
k++;
l = i;
r = start + k - 1;
z[i] = initial + k;
}
}
}
// cout<<s.size()<<" "<<n<<endl;
// for(auto c : s)
// cout<<c<<" ";
// cout<<endl;
// for(int i = 0; i < s.size(); i++){
// cout<<z[i]<<" ";
// }
// cout<<endl;
vector<int>aparitii;
for(int i = a.size() + 1; i < n; i++){
if(z[i] >= a.size()){
// cout<<i - a.size() - 1<<" ";
aparitii.push_back(i - a.size() - 1);
}
}
out<<aparitii.size()<<'\n';
int sz = aparitii.size();
for(int i = 0; i < min(1000,sz); i++)
out<<aparitii[i]<<" ";
}
int main()
{
in>>a>>b;
s = a + '#' + b;
zalgorithm();
return 0;
}