Advertisement
Guest User

Untitled

a guest
Feb 13th, 2018
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.32 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <string>
  4. #include <vector>
  5. #include <stdlib.h>
  6.  
  7. using namespace std;
  8.  
  9. vector<int> prefixFunc(string s) {
  10. auto n = (int) s.length();
  11. vector<int> pi(n);
  12. for (int i=1; i<n; ++i) {
  13. int j = pi[i-1];
  14. while (j > 0 && s[i] != s[j])
  15. j = pi[j-1];
  16. if (s[i] == s[j]) ++j;
  17. pi[i] = j;
  18. }
  19. return pi;
  20. }
  21.  
  22.  
  23. vector<int> getSubstrings(const string &string1, const string &sub1) {
  24. int stringl = string1.length();
  25. int subl = sub1.length();
  26. vector<int> result;
  27. vector<int> borders = prefixFunc(sub1+"$"+string1);
  28. int count = 0;
  29. result.push_back(0);
  30. for (int i = 0; i < stringl; i++)
  31. {
  32. if (borders[subl + i + 1] == subl) {
  33. result.push_back(i-subl+1);
  34. count++;
  35. }
  36. }
  37. result[0] = count;
  38.  
  39. return result;
  40. }
  41.  
  42. int main()
  43. {
  44. string t;
  45. string p;
  46. vector<int> res;
  47.  
  48. ifstream fin;
  49. fin.open("input.txt");
  50. if (fin.is_open())
  51. {
  52. getline(fin, t);
  53. getline(fin, p);
  54. fin.close();
  55. }
  56.  
  57. res = getSubstrings(t, p);
  58.  
  59. fstream fout;
  60. fout.open("output.txt", ios::out);
  61. fout << res.size() << "\n";
  62. for (std::vector<int>::const_iterator i = res.begin(); i != res.end(); ++i)
  63. fout << *i << "\n";
  64. fout.close();
  65.  
  66. return 0;
  67. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement