Pagini recente » Cod sursa (job #412091) | Cod sursa (job #1147205) | Cod sursa (job #2791016) | Cod sursa (job #2861236) | Cod sursa (job #3290916)
#ifndef LOCAL
#pragma GCC optimize("O3")
// #pragma GCC target("avx2")
#endif
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
using ll = long long;
using ci = const int;
using cll = const long long;
using namespace std;
/*******************************/
// INPUT / OUTPUT
#ifndef LOCAL
ifstream in("strmatch.in");
ofstream out("strmatch.out");
#define cin in
#define cout out
#endif
/*******************************/
/// GLOBAL DECLARATIONS
string A, B;
/*******************************/
/// FUNCTIONS
void ReadInput();
void Solution();
void Output();
/*******************************/
///-------------------------------------
inline void ReadInput()
{
cin >> A >> B;
}
///-------------------------------------
vector<int> KMP(string s) {
const int n = s.size();
vector<int> kmp(n, 0);
kmp[0] = 0; // tragem muchie (-1, 0)
kmp[1] = (s[0] == s[1] ? 1 : 0); // 1 daca s[0] == s[1], 0 altfel
// in funcite de caz, tragem muchie (-1, 1) sau (0, 1)
for(int i = 2; i < n; i++) {
int se_trage_din = kmp[i - 1];
while(se_trage_din > 0 && s[se_trage_din] != s[i]) {
se_trage_din = kmp[se_trage_din - 1];
}
if(s[se_trage_din] == s[i]) {
kmp[i] = se_trage_din + 1;
} else {
kmp[i] = 0;
}
}
return kmp;
}
///-------------------------------------
inline vector<int> get_aparitii(vector <int> &kmp)
{
vector <int> aparitii;
for (int i = 0 ; i < kmp.size() ; ++ i)
{
if (kmp[i] == A.length())
{
aparitii.push_back((i - (A.length() + 1)) - A.length() + 1);
}
}
return aparitii;
}
///-------------------------------------
inline void Solution()
{
auto kmp = KMP(A + "#" + B);
auto aparitii = get_aparitii(kmp);
cout << aparitii.size() << "\n";
for (int i = 0 ; i < min(int(aparitii.size()), 1000) ; ++ i) cout << aparitii[i] << " ";
}
///-------------------------------------
inline void Output()
{
}
///-------------------------------------
int main()
{
#ifndef LOCAL
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
#endif
ReadInput();
Solution();
Output();
return 0;
}