Pagini recente » Cod sursa (job #2114457) | Cod sursa (job #2987094) | Cod sursa (job #1474663) | Cod sursa (job #2947722) | Cod sursa (job #2675099)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int N = 2000041;
int lps[N];
char s1[N], s2[N];
int ans1 = 0;
vector<int> ans2;
void make_lps(){
int j = 0;
for(int i = 1; s1[i] != '\0'; ++i){
if(s1[i] == s1[j]){
lps[i] = ++j;
}else if(j != 0){
j = lps[j-1];
i--;
}
}
}
void solve(){
int j = 0;
for(int i = 0; s2[i] != '\0'; ++i){
if(s1[j] == s2[i]){
j++;
if(s1[j] == '\0'){
ans1++;
if(ans1 <= 1000)ans2.push_back(i-j+1);
j = lps[j-1];
}
}else if(j != 0){
j = lps[j-1];
i--;
}
}
}
int main(){
// ios_base::sync_with_stdio(false);
fin >> s1 >> s2;
make_lps();
solve();
fout << ans1 << "\n";
for(auto a : ans2)fout << a << " ";
return 0;
}