Find the length of the longest common substring with queries

→ Обратите внимание

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
38:31:50
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя Mr.Awesome

Find the length of the longest common substring with queries

Автор Mr.Awesome, история, 5 лет назад, По-английски

Here's a problem I crossed lately:

You have a large String S, and q queries, each query consist of a small string b.

The answer of each query is to find the length of the longest common substring between S and b. ( |S| <= 10^5, |b| <= 100, q <= 100 )

My dp solution to find the length of the largest LCS is O(n*m) per query, but it doesn't seem to pass!

I think will need to do some pre-prcessing of S before starting quering, but I can't find a solution.

Any hint or idea will be appreciated.

#strings, substring, #lcs, #hashing

Mr.Awesome
5 лет назад
9

Комментарии (9)

Написать комментарий?

eulerkochy

5 лет назад, # |

I guess it's a standard application of Suffix Trees. Build a suffix tree for S$b# and then query for the LCS in O(|S|+|b|) for each query. And that should be fast enough, given the constraints.

Read more about it here

→ Ответить

Not-Afraid

5 лет назад, # |

You can use hashing. Let the original string be s.
First precompute and store hash (in a 2d vector let's say) for every substring of (size from $$$1$$$ to $$$100$$$) string s. Now for every query hash the current string, and look any of it's substring hash is present in precomputed vector of it's size.

→ Ответить

Mr.Awesome

5 лет назад, # ^ |

Thanks for your reply, but isn't the complexity of this is 100 * |S| * (complexity of hashing each substring) ? Is this a right code for your solution ?

for(int i = 0; i < S.length(); i++) {
    string tmp = "";
    for(int j = i; j < min(S.length(), i + 100); j++) {
        tmp += s[j];
        hash_and_add_to_vector(tmp);
     }
}

→ Ответить

Not-Afraid

5 лет назад, # ^ |

← Rev. 2 →

Spoiler

const int N = 1e5 + 5;
vector<int> v[N];
char s[N];
// step 1) First precalculate hash of string s;

// step 2) Storing hash of every string of size atmost 100
// almost 1e7 operations here 
for (int i = 1; i <= 1e5; ++i) { // consider 1-based indexing
  for (int j = i; j > 0 && j >= i - 100; --j) {
    int size = i - j + 1;
    // hash (j,i) is a function which gives hash of substring s[j..i] which is O(1)
    v[size].push_back(hash(j,i));
  }
}

// q * k * k
// a string of size k will have almost k^2 substring
for (int i = 1; i <= q; ++i) {
  cin >> curr_string;
  //step 1) Compute it's hash
  
  //step 2) 
  for (int j = 0; j < curr_string.size(); ++j) {
    for (int k = j; k < curr_string.size(); ++k) {
      int cur_size = k - j + 1;
      int has = hash(j,k);
      if (has is present in v[cur_size]) {
        // Answer is found
      }
    }
  }
}

→ Ответить