Advertisement
Guest User

Untitled

a guest
Oct 13th, 2019
125
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.28 KB | None | 0 0
  1. #include <cstdio>
  2. #include <string>
  3. #include <vector>
  4. #include <sstream>
  5. #include <iostream>
  6.  
  7. using namespace std;
  8.  
  9. vector<int> makeTable(string pattern) {
  10. int strsize = pattern.size();
  11. vector<int> table(strsize);
  12.  
  13. int j = 0;
  14. for(int i=1; i<strsize; i++) {
  15. while(j > 0 && pattern[i] != pattern[j]) {
  16. j = table[j-1];
  17. }
  18. if(pattern[i] == pattern[j]) {
  19. table[i] = ++j;
  20. }
  21. }
  22.  
  23. return table;
  24. }
  25.  
  26. void KMP(string parent, string pattern) {
  27. int prsize = parent.size();
  28. int ptsize = pattern.size();
  29. int j = 0;
  30. vector<int> table = makeTable(pattern);
  31. vector<int> ans;
  32. for(int i=0; i<prsize; i++) {
  33. while(j > 0 && parent[i] != pattern[j]) {
  34. j = table[j-1];
  35. }
  36. if(parent[i] == pattern[j]) {
  37. if(j == ptsize-1) {
  38. ans.push_back(i-ptsize+2);
  39. j = table[j];
  40. }
  41. else {
  42. j++;
  43. }
  44. }
  45. }
  46.  
  47. cout << ans.size() << '\n';
  48. for(int i=0; i<ans.size(); i++) {
  49. cout << ans[i] << '\n';
  50. }
  51. }
  52.  
  53. int main(void) {
  54. ios_base::sync_with_stdio(false);
  55. cin.tie(0);
  56.  
  57. string parent, pattern;
  58. getline(cin, parent);
  59. getline(cin, pattern);
  60.  
  61. KMP(parent, pattern);
  62.  
  63. return 0;
  64. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement