Pagini recente » Cod sursa (job #1382965) | Cod sursa (job #536357) | Cod sursa (job #39156) | Cod sursa (job #2585272) | Cod sursa (job #3195434)
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits.h>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
using namespace std;
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define endl '\n'
void debug(vector<int> v)
{
for(int i = 0;i < (int)v.size();i++) {cout << v[i] << ' ';}
cout << endl;
}
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
signed main()
{
string a, b; fin >> a >> b;
a += "#";
a += b;
//cout << a << endl;
int sz_init = a.size() - b.size() - 1;
int n = a.size();
vector<int> kmp(n, 0);
vector<int> ans_pos;
int it = 0;
int ans = 0;
for(int i = 1;i < n;i++)
{
while(it > 0 and a[it] != a[i])
{
it = kmp[it - 1];
}
//cout << "la pos: " << i << " it: " << it << endl;
//cout << "a[i]: " << a[i] << " a[it]: " << a[it] << endl;
if(a[i] == a[it])
{
//cout << "-->>>> " << endl;
it++;
}
kmp[i] = it;
if(it == sz_init)
{
ans_pos.push_back(i - 2 * sz_init);
ans++;
}
//cout << kmp[i] << " ";
}
fout << ans << endl;
for(int i = 0;i < min(1000, (int)ans_pos.size());i++) fout << ans_pos[i] << " ";
return 0;
}