Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement