fork download
  1. #include <iostream>
  2. #include <map>
  3. using namespace std;
  4.  
  5. struct state {
  6. int len, link;
  7. map <char,int> next;
  8. };
  9.  
  10. state st[2*100000];
  11. int sz, last;
  12.  
  13. void sa_init() {
  14. sz = 0;
  15. last = 0;
  16. st[0].len = 0;
  17. st[0].link = -1;
  18. sz++;
  19. }
  20.  
  21. void sa_extend (char c) {
  22. int cur = sz++;
  23. st[cur].len = st[last].len + 1;
  24. int p;
  25. for (p = last; p != -1 && !st[p].next.count(c); p = st[p].link) st[p].next[c] = cur;
  26. if (p == -1) st[cur].link = 0;
  27. else {
  28. int q = st[p].next[c];
  29. if (st[p].len + 1 == st[q].len) st[cur].link = q;
  30. else {
  31. int clone = sz++;
  32. st[clone].len = st[p].len + 1;
  33. st[clone].next = st[q].next;
  34. st[clone].link = st[q].link;
  35. st[q].link = st[cur].link = clone;
  36. }
  37. }
  38. last = cur;
  39. }
  40.  
  41. int longer_common_string (string a, string b) {
  42. sa_init();
  43. for (int i = 0; i < a.length(); i++) sa_extend (a[i]);
  44. int v = 0, l = 0, best = 0, bestpos = 0;
  45. for (int i = 0; i < b.length(); i++) {
  46. while (v != 0 && ! st[v].next.count(b[i])) {
  47. v = st[v].link;
  48. l = st[v].len;
  49. }
  50. if (st[v].next.count(b[i])) {
  51. v = st[v].next[b[i]];
  52. l++;
  53. }
  54. if (l > best){
  55. best = l;
  56. bestpos = i;
  57. }
  58. }
  59. return best;
  60. }
  61.  
  62. int main() {
  63. string a, b;
  64. int n;
  65. cin >> a >> b >> n;
  66. if (longer_common_string(a, b) >= n) cout << "YES";
  67. else cout << "NO";
  68. return 0;
  69. }
Success #stdin #stdout 0s 26176KB
stdin
aaaaaka
aka
3
stdout
YES