Pagini recente » Cod sursa (job #329997) | Cod sursa (job #1601669) | Cod sursa (job #2709859) | Cod sursa (job #540535) | Cod sursa (job #1500434)
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
void make_pi(const string& str, vector<int>& pi){
const int n = str.size();
pi.resize(n, 0);
for(int i = 1; i < n; ++i){
for(pi[i] = pi[i-1];
pi[i] && str[i] != str[pi[i]];
pi[i] = pi[pi[i]-1]);
if(str[i] == str[pi[i]]){
++pi[i]; } } }
int main(){
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string str;
f >> str;
const int first_size = str.size();
str.push_back('#');
const int st_poz = str.size();
for(char ch; f >> ch; ){
str.push_back(ch); }
vector<int> pi;
make_pi(str, pi);
vector<int> rez;
for(int i = 0; st_poz+i < str.size(); ++i){
if(pi[st_poz+i] == first_size){
rez.push_back(i+1-first_size); } }
g << rez.size() << '\n';
for(const auto x : rez){
g << x << ' '; }
return 0; }