Pagini recente » Cod sursa (job #1319672) | Cod sursa (job #2855103) | Cod sursa (job #61495) | Cod sursa (job #673162) | Cod sursa (job #2773683)
#include <bits/stdc++.h>
#define dbg(x...) cout << "[" << #x << "] = [ "; _dbg(x); cout << "]\n"
using namespace std;
template <typename T>void _dbg(T t){cout << t << " ";}template<typename T, typename... Args>void _dbg(T t, Args... args) {cout << t << " , ";_dbg(args...) ;}template <typename T, typename V>ostream& operator<<(ostream& os, const pair<T,V> p){cout << "(" << p.first << "," << p.second << ")";}template <template <typename...> class Container, typename... Types>ostream& operator<<(ostream& os, const Container<Types...> &dt){cout << "{";auto preEnd = dt.end();preEnd--;for (auto bgn = dt.begin(); bgn != preEnd; bgn++)cout << *bgn << ",";cout << *preEnd << "}";return os;}ostream& operator<<(ostream& os, const string &dt){cout << "{";auto preEnd = dt.end();preEnd--;for (auto bgn = dt.begin(); bgn != preEnd; bgn++)cout << *bgn;cout << *preEnd << "}";return os;}
ifstream in("strmatch.in");
ofstream out("strmatch.out");
vector<int> kmpPre(string s)
{int i;
vector<int> pre(s.size() , 0);
for (i = 1; i < s.size(); i++) {
int k = pre[i - 1];
while (k > 0 && s[i] != s[k]) {
k = pre[k - 1];
}
if (s[k] == s[i])
k++;
pre[i] = k;
}
return pre;
}
string s,t;
void input()
{
in >> t >> s;
// dbg(s,t);
}
void solve()
{
int j = 0,n = s.size(),i;
vector<int> pre = kmpPre(t),matches;
for (int i = 0; i < n;) {
//dbg(i,j);
if (s[i] == t[j]) {//cout << "MATCH\n\n";
i++;
j++;
if (j == t.size()) {
matches.push_back(i - t.size());
j = pre[j - 1];
}
}
else
{
if (j != 0)
j = pre[j - 1];
else
i++;
}
}
out << matches.size() << "\n";
for (i = 0; i < min(1000 , (int)matches.size()); i++)
out << matches[i] << " ";
out << "\n";
}
int main()
{int t = 1;
while (t--) {
input();
solve();
}
}