Pagini recente » Cod sursa (job #2925499) | Cod sursa (job #2613615) | Cod sursa (job #507678) | Cod sursa (job #668350) | Cod sursa (job #2616180)
#include <iostream>
#include <fstream>
const int MAXN = 2e6 + 1;
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string s;
string a,b;
int z[MAXN];
void Z(){
int n = s.size();
int l = 0,r = 0;
int cnt = 0;
z[0] = s.size();
for(int i = 1; i < n; i++){
if(i > r){
int cnt = 0;
while(i + cnt < n && s[i + cnt] == s[cnt])
cnt++;
z[i] = cnt;
l = i;
r = i + cnt - 1;
}else{
if(z[i - l] + i < r){
z[i] = z[i - l];
}else{
z[i] = min(z[i - l],r - i + 1);
int capat = i + z[i],cnt = 0;
int inceput = z[i];
//if(z[i] == 0)
//capat++;
while(capat + cnt < n && s[capat + cnt] == s[cnt + inceput])
cnt++;
z[i] += cnt;
l = i;
r = capat + cnt;
}
}
if(z[i] == a.size())
cnt++;
}
// cout<<" ";
// for(int i = 1; i < n; i++){
// cout<<z[i];
// }
out<<cnt<<"\n";
for(int i = 0; i < n; i++){
if(z[i] == a.size()){
out<<i - a.size() - 1<<" ";
}
}
}
int main()
{
in>>a>>b;
s = a + '#' + b;
//cout<<s<<endl;
Z();
return 0;
}