Pagini recente » Cod sursa (job #2133569) | Cod sursa (job #2049732) | Cod sursa (job #361587) | Cod sursa (job #2848735) | Cod sursa (job #2616189)
#include <iostream>
#include <fstream>
const int MAXN = 4e6 + 4;
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 cate_sunt = 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];
while(capat + cnt < n && s[capat + cnt] == s[cnt + inceput])
cnt++;
z[i] += cnt;
l = i;
r = capat + cnt;
}
}
if(z[i] == a.size()){
if(cate_sunt + 1 <= 1000)
cate_sunt++;
}
}
out<<cate_sunt<<"\n";
for(int i = 0; i < n; i++){
if(z[i] == a.size() && cate_sunt){
cate_sunt--;
out<<i - a.size() - 1<<" ";
}
}
}
int main()
{
in>>a>>b;
// a = 'A';
// for(int i = 1; i <= 2000; i++)
// b += 'A';
s = a + '#' + b;
Z();
return 0;
}