Advertisement
Guest User

Untitled

a guest
Oct 14th, 2019
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.64 KB | None | 0 0
  1. #include <cstdio>
  2. #include <vector>
  3. #include <string>
  4. #include <iostream>
  5.  
  6. using namespace std;
  7.  
  8. vector<int> makeTable(string pattern) {
  9. int strsize = pattern.size();
  10. vector<int> table(strsize);
  11. int j = 0;
  12.  
  13. for(int i=1; i<strsize; i++) {
  14. while(j > 0 && pattern[i] != pattern[j]) {
  15. j = table[j - 1];
  16. }
  17. if(pattern[i] == pattern[j]) {
  18. table[i] = ++j;
  19. }
  20. }
  21.  
  22. return table;
  23. }
  24.  
  25. int main(void) {
  26. ios_base::sync_with_stdio(false);
  27.  
  28. int n;
  29. string pattern;
  30. cin >> n >> pattern;
  31.  
  32. vector<int> table = makeTable(pattern);
  33. cout << n - table[n - 1] << '\n';
  34. return 0;
  35. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement