fork download
copy 
  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
comments (?)
stdin
copy 
aaaaaka
aka
3
stdout
copy 
YES
https://ideone.com/ilwb4e
Длина общей подстроки
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!