Advertisement
LA77

Untitled

Feb 25th, 2025
9
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.45 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define pb push_back
  3. #define pii pair<int, int>
  4. using ll = long long;
  5.  
  6. using namespace std;
  7.  
  8. const int NMAX = 2e6 + 5;
  9. /*******************************/
  10. // INPUT / OUTPUT
  11.  
  12. ifstream f("strmatch.in");
  13. ofstream g("strmatch.out");
  14. /*******************************/
  15. /// GLOBAL DECLARATIONS
  16.  
  17. string A, B;
  18. int N, M;
  19. string s;
  20. int pi[2 * NMAX];
  21. vector <int> sol;
  22. /*******************************/
  23. /// FUNCTIONS
  24.  
  25. void ReadInput();
  26. void Solution();
  27. void Output();
  28. /*******************************/
  29. ///-------------------------------------
  30. inline void ReadInput()
  31. {
  32. f >> A >> B;
  33. N = int(A.length()), M = int(B.length());
  34. s = A + "#" + B;
  35. }
  36. ///-------------------------------------
  37. inline void Solution()
  38. {
  39. int j;
  40. for (int i = 1 ; i < s.length() ; ++ i)
  41. {
  42. j = pi[i - 1];
  43. while (j > 0 && s[i] != s[j])
  44. j = pi[j - 1];
  45. if (s[i] == s[j])
  46. j ++;
  47. pi[i] = j;
  48. if (pi[i] == N)
  49. {
  50. sol.push_back(i - 2 * N);
  51. }
  52. }
  53. }
  54. ///-------------------------------------
  55. inline void Output()
  56. {
  57. g << sol.size() << "\n";
  58. for (int i = 0 ; i < min(1000, int(sol.size())) ; ++ i)
  59. {
  60. g << sol[i] << " ";
  61. }
  62. }
  63. ///-------------------------------------
  64. int main()
  65. {
  66. ios::sync_with_stdio(false);
  67. cin.tie(NULL);
  68. cout.tie(NULL);
  69. ReadInput();
  70. Solution();
  71. Output();
  72. return 0;
  73. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement