Pagini recente » Cod sursa (job #1146120) | Cod sursa (job #1148541) | Cod sursa (job #3005093) | Cod sursa (job #3212643) | Cod sursa (job #3290912)
#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 = i - 1;
// stiu ca s[0..kmp[se_trage_din]] == s[i - kmp[se_trage_din]..i - 1]
// daca as avea s[kmp[se_trage_din] + 1] == s[i], as putea sa zic ca
// kmp[i] = kmp[se_trage_din] + 1
// altfel, se_trage_din trebuie sa fie nu el insasi
// ci kmp[se_trage_din] -> pozitia precedenta la care aveam acelasi sufix
while(s[i] != s[kmp[se_trage_din]]) {
se_trage_din = kmp[se_trage_din - 1];
if(se_trage_din == 0) break;
}
if(se_trage_din == 0 && s[i] != s[0]) {
kmp[i] = 0;
// tragem muchie (-1, i)
continue;
}
kmp[i] = 1 + kmp[se_trage_din];
// tragem muchie (se_trage_din, i)
}
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;
}