Advertisement
vladm98

Untitled

Aug 8th, 2017
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.24 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. char s[4000005];
  5. long long counter, raspuns[1001];
  6. int z[4000005];
  7. void Z_Algorithm (int lungime, int n)
  8. {
  9. z[1] = 0;
  10. int l, r;
  11. l = r = 1;
  12. for (int i = 2; i<=n; ++i)
  13. {
  14. if (i > r)
  15. {
  16. while (z[i] + i <= n && s[z[i]+i] == s[z[i]+1]) ++z[i];
  17. l = i;
  18. r = i + z[i] - 1;
  19. }
  20. else
  21. {
  22. if (i+z[i-l+1]-1 < r)
  23. z[i] = z[i-l+1];
  24. else
  25. {
  26. z[i] = r-i;
  27. while (z[i] + i <= n && s[z[i]+i] == s[z[i]+1]) ++z[i];
  28. l = i;
  29. r = i + z[i] - 1;
  30. }
  31. }
  32. if (z[i] == lungime)
  33. {
  34. ++counter;
  35. if (counter <= 1000)
  36. raspuns[counter] = i-lungime-2;
  37. }
  38. }
  39. }
  40. int main()
  41. {
  42. ifstream fin ("strmatch.in");
  43. ofstream fout ("strmatch.out");
  44. int n, i, len;
  45. fin >> (s+1);
  46. len = strlen (s+1);
  47. s[len+1] = '#';
  48. fin >> (s+len+2);
  49. n = strlen(s+1);
  50. Z_Algorithm(len, n);
  51. fout << counter << '\n';
  52. for (int i = 1; i<=counter && i <=1000; ++i)
  53. fout << raspuns[i] << " ";
  54. return 0;
  55. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement