Pagini recente » Cod sursa (job #2804771) | Cod sursa (job #2712084) | Cod sursa (job #2249050) | Cod sursa (job #708412) | Cod sursa (job #2933951)
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
using ll = long long;
using namespace std;
const int NMAX = 2e6 + 5;
/*******************************/
// INPUT / OUTPUT
ifstream f("strmatch.in");
ofstream g("strmatch.out");
/*******************************/
/// GLOBAL DECLARATIONS
string A, B;
int N, M;
string s;
int pi[2 * NMAX];
vector <int> sol;
/*******************************/
/// FUNCTIONS
void ReadInput();
void Solution();
void Output();
/*******************************/
///-------------------------------------
inline void ReadInput()
{
f >> A >> B;
N = int(A.length()), M = int(B.length());
s = A + "#" + B;
}
///-------------------------------------
inline void Solution()
{
int j;
for (int i = 1 ; i < s.length() ; ++ i)
{
j = pi[i - 1];
while (j > 0 && s[i] != s[j])
j = pi[j - 1];
if (s[i] == s[j])
j ++;
pi[i] = j;
if (pi[i] == N)
{
sol.push_back(i - 2 * N);
}
}
}
///-------------------------------------
inline void Output()
{
g << sol.size() << "\n";
for (int i = 0 ; i < min(1000, int(sol.size())) ; ++ i)
{
g << sol[i] << " ";
}
}
///-------------------------------------
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ReadInput();
Solution();
Output();
return 0;
}