Advertisement
sve_vash

Untitled

Jul 3rd, 2019
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.15 KB | None | 0 0
  1. #include <fstream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. int main() {
  7. string t, s;
  8.  
  9. ifstream inp("input.txt");
  10.  
  11. getline(inp, s);
  12. getline(inp, t);
  13.  
  14. inp.close();
  15.  
  16. int n = t.size();
  17. vector<int> pi (n);
  18. for (int i = 1; i < n; ++i) {
  19. int k = pi[i - 1];
  20. while (k > 0 && t[i] != t[k])
  21. k = pi[k - 1];
  22. if (t[i] == t[k])
  23. ++k;
  24. pi[i] = k;
  25. }
  26. //bool onechar = false;
  27. //if (t.size() == 1)
  28. // onechar = true;
  29. int pos = -1, q = 0;
  30. for (int i = 0; i < s.size(); ++i) {
  31. //if (onechar) {
  32. // if (t[0] == s[i]) {
  33. // ofstream out("output.txt");
  34. // out << i + 1;
  35. // out.close();
  36. // return 0;
  37. // }
  38. //}
  39. while (q > 0 && t[q] != s[i]) {
  40. q = pi[q-1];
  41. }
  42. if (t[q] == s[i]) {
  43. q++;
  44. }
  45. if(q == t.size()) {
  46. pos = i - q + 2;
  47. break;
  48. }
  49. }
  50.  
  51.  
  52. ofstream out("output.txt");
  53. //if (onechar) {
  54. // out << "-1";
  55. //}
  56. //else {
  57. out << pos;
  58. //}
  59. out.close();
  60. return 0;
  61. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement