Show all threads Hide all threads Show all messages Hide all messages  (SPOILER) My solution  Alikhan Zimanov  1713. Key Substrings  5 Jun 2020 11:38  1  My solution is based on string hashing. Let's say that the strings from the input are s[1], s[2], ... , s[n]. First, let's iterate over all possible lengths from 1 to 100 (since the maximal length of a string is 100). Let's fix some length "len" and create a vector "all" which will contain all possible hashes of substrings of length "len" of all the strings s[i]. Additionally, for each i from 1 to n create a vector a[i] which will contain the hashes of substrings of length "len" of only the string s[i]. Now, sort all the vectors we've created so that we could binary search on them. Finally, go through each i from 1 to n and then for each of the substrings of s[i], using binary search count the number of occurrences of its hash in the vector "all" and the vector a[i]. If these numbers are equal, then this substring occurred only in the string s[i] and can be used as a key substring. By changing the base and modulo of the hash, you can pass the WA caused by collision of hashes (I used p = 2313 and mod = 1000000123). The time complexity will be O(max_len * n^2 * log(n)), where max_len is the maximal length of a string.  WA test 2  andrei parvu  1713. Key Substrings  27 Mar 2020 11:04  6  Can somebody tell me how they passed test nr. 2 (or give me some good test cases)? I have a solution in O(N*M*log(N*M)) using suffix array and I can't find the bug. Thanks Edited by author 16.09.2010 22:39 I've got absolutely the same problem. I use suffix and lcp arrays. I use the following algo: for i = 1 to LENGTH_OF_ALL_WORDS l = the closest preceding suffix that belong to another word r = the closest succeeding suffix that belong to another word v = max(lcp(l, i), lcp(i, r)) + 1; w = the word that contains suffix i; if (v < ans[w]) ans[w] = v; I've tried lots of tests but can't find what's wrong. There is something strange with this problem. I hasn't written suffix array building on my own, I used a reference implementation. Looking for a bug I replaced it with code that builds suffix array in the naive way (i.e. literally sorting suffixes). I got AC! So there are 2 results:  The reference implementation I used is wrong :)  The test data seems to be weak because naive suffix and LCP arrays building gets AC. TO VC15 (Orel STU) max(lcp(l, i), lcp(i, r)) + 1 may longer than the word‘s length Edited by author 29.06.2012 13:49 Yes, it could be. In this case I don't change the answer for the word. 2 qwertyuiopasdfghjklzxcvbnm qwezrtyuiopasdfghjklzxcvbnmer  WA3  pizdec  1713. Key Substrings  15 Aug 2018 14:22  1  WA3 pizdec 15 Aug 2018 14:22 I use suffix array but WA3. Give me some tests. #include <string> #include <iostream> using namespace std; int min(int x, int y) { return x < y ? x : y; } int max(int x, int y) { return x > y ? x : y; } int Min(int l, int r); const int nmax = 1005; const int maxlen = 1000 * 105; const int alphabet = 256; int n, m, sum; int p[maxlen], cnt[maxlen], c[maxlen]; int pn[maxlen], cn[maxlen], lcp[maxlen]; int who[maxlen], up[maxlen], down[maxlen], a[nmax], b[nmax]; int ans_len[nmax], ans_ind[nmax]; string s, str[nmax]; int main() { cin>>m; for(int i=0;i<m;i++) cin>>str[i], s+=str[i]; m++; str[m1]="#"; s+=str[m1];
n = s.length(); memset(cnt, 0, alphabet * sizeof(int)); for (int i = 0; i<n; ++i) ++cnt[s[i]]; for (int i = 1; i<alphabet; ++i) cnt[i] += cnt[i  1]; for (int i = 0; i<n; ++i) p[cnt[s[i]]] = i; c[p[0]] = 0; int classes = 1; for (int i = 1; i<n; ++i) { if (s[p[i]] != s[p[i  1]]) ++classes; c[p[i]] = classes  1; } for (int h = 0; (1 << h)<n; ++h) { for (int i = 0; i<n; ++i) { pn[i] = p[i]  (1 << h); if (pn[i] < 0) pn[i] += n; } memset(cnt, 0, classes * sizeof(int)); for (int i = 0; i<n; ++i) ++cnt[c[pn[i]]]; for (int i = 1; i<classes; ++i) cnt[i] += cnt[i  1]; for (int i = n  1; i >= 0; i) p[cnt[c[pn[i]]]] = pn[i]; cn[p[0]] = 0; classes = 1; for (int i = 1; i<n; ++i) { int mid1 = (p[i] + (1 << h)) % n, mid2 = (p[i  1] + (1 << h)) % n; if (c[p[i]] != c[p[i  1]]  c[mid1] != c[mid2]) ++classes; cn[p[i]] = classes  1; } memcpy(c, cn, n * sizeof(int)); } n, m, s.erase(n, 1); for (int i = 0; i < n; i++) p[i] = p[i + 1]; sum = 0; for (int i = 0; i < m; i++) a[i]=sum, b[i]=sum+str[i].length()1, sum += str[i].length();
for (int i = 0; i < n; i++) { int j = 0; while (!(a[j] <= p[i] && p[i] <= b[j])) j++; who[i] = j; }
for (int i = 0; i <= n  2; i++) { lcp[i] = 0; int hr = max(p[i], p[i+1]); int gr = min(b[who[i]]p[i]+1, b[who[i+1]]p[i+1]+1); while (hr+lcp[i]<n && lcp[i]<gr && s[p[i] + lcp[i]] == s[p[i + 1] + lcp[i]]) lcp[i]++; } down[0] = 1; for (int i = 1; i < n; i++) down[i] = who[i  1] == who[i]? down[i  1] : i  1;
up[n  1] = 1; for (int i = n  2; i >= 0; i) up[i] = who[i + 1] == who[i] ? up[i + 1] : i + 1; for (int i = 0; i < m; i++) ans_len[i] = str[i].length(), ans_ind[i]=a[i]; for (int i = 0; i < n; i++) { int val1 = down[i] == 1 ? 0 : Min(down[i], i  1); int val2 = up[i] == 1 ? 0 : Min(i, up[i]1); int now_len = max(val1, val2) + 1; if (now_len<=b[who[i]]p[i]+1 && ans_len[who[i]] > now_len) ans_len[who[i]] = now_len, ans_ind[who[i]] = p[i]; } for (int i = 0; i < m; i++) { for (int j = 0; j < ans_len[i]; j++) cout << s[ans_ind[i] + j]; if(i+1<m) cout << endl; } return 0; } int Min(int l, int r) { int res=maxlen+5; for(int i=l;i<=r;i++) res=min(res, lcp[i]); return res; } Edited by author 16.08.2018 00:42  Hash is not working. HELP!  Pavel Kovalenko  1713. Key Substrings  11 Mar 2018 02:44  3  If i use hashtable, i get WA. Because due to the small MOD ~10^6, i get probably a coincidence of some hashes. (I used the degree = 31 and tried modules 1000003,... etc.) If i use simply linear hash (in common vector) and sorting i get TL. If i keep hash of each string in separate vectors, and then use a binary search, then again i get TL. :( I got a lot of TLE while using vector... then I changed it to simple array and got Ac. Hash works just fine (h = h*P + n, where h is size_t, P is some prime, and n is the next char), but you need to keep the loop order: for each length first go thru all substrings to fill unordered_map<substring,int> and then for each nonanswered command and all its substrings of the current length check if they have been seen only in this command. Note that the hash can be rolled from one substring of fixed length to the next and it seems equal_to can always return true (tried for P=127).  if you have wa#7  Baurzhan  1713. Key Substrings  13 Aug 2017 20:07  2  try this test 2 abab baa answer: ab aa  =(  Dima Kravtsov  1713. Key Substrings  11 Jul 2017 18:06  10  =( Dima Kravtsov 11 Oct 2009 21:45 Please, give me some hints on how to solve it. Thanks in advance. Re: =( Vedernikoff Sergey (HSE: АОП) 12 Oct 2009 23:35 Re: =( Igor9669(Tashkent IAC) 12 Oct 2009 23:57 I also use hash,but TLE 3 =( My complexity is O(N*MaxLen^2*logN). What is your? Edited by author 13.10.2009 00:06 Re: =( Victor Barinov (TNU) 13 Oct 2009 15:47 Try use hash table to avoid logN Re: =( Vedernikoff Sergey (HSE: АОП) 14 Oct 2009 16:55 My complexity is O(N^2*M^2*(logN+logM)), where M is maximal length of a word. It passes TL due to small constant. P.S. You don't need hash tables to avoid N. Just one linear hash and sorting. Edited by author 14.10.2009 20:41 Re: =( Igor9669(Tashkent IAC) 16 Oct 2009 12:41 Re: =( Mahilewets 11 Jul 2017 16:21 (N^2)*(M^2)*(logN+logM)? When N=1e3 and M=1e2? Accepted? Anybody knows how it was done? Edited by author 11.07.2017 16:23 Re: =( Mahilewets 11 Jul 2017 18:06 So, I understood If explicitly sort suffixes of string command1+command command2+command3+... we have upper bound N^2*M^2 but actual number of comparisons is smaller Re: =( Petr Nikishin 5 Apr 2010 07:58 This problem can be very simply solved using standard techniques of suffix array + lcp array. Complexity is O(N * M * logN), M  length of the longest string. Due to allround using of STL my solution works in 0.25, but this time can be hugely improved. SkorKNURE Edited by author 05.04.2010 08:00 Re: =( xurshid_n 15 Jan 2012 23:01 This problem can be very simply solved using standard techniques of suffix array + lcp array. Complexity is O(N * M * logN), M  length of the longest string. Due to allround using of STL my solution works in 0.25, but this time can be hugely improved. SkorKNURE Edited by author 05.04.2010 08:00 You are right! I Ac! 0.046 s. Thanks!  Don't waste your time to binary search without hash  Mahilewets  1713. Key Substrings  10 Jul 2017 19:06  2  I was trying to do the following. Construct suffix automation for each command. Binary search for length of each key substring. Binary search works as follows. For each substring of command of len (lower_bound+upper_bound) /2 check whether it is a substring of another command. And it was Time Limit Exceed #7. So, don't repeat yourself. Find better solution. Probably with suffix array, as posted on the webboard.  WA test 3  Lament of the Highborne  1713. Key Substrings  20 Sep 2016 07:35  1  WA test 3 Lament of the Highborne 20 Sep 2016 07:35 I got WA on test 3 and cant find error on my code despire of using lots of random test. I using suffix array and lcp. Can anyone give me any test to check :(  wa #7  Baurzhan  1713. Key Substrings  6 May 2015 20:16  5  wa #7 Baurzhan 3 Nov 2010 15:38 I'm afraid that i'm getting WA on 7th test because of hash collisions. How to avoid it? Please, give me some recipes) I tried to change prime base  31,43,57  anyway WA#7. Edited by author 07.11.2010 10:15 P=1000000007  only this base helped me! 31,57  and other small bases  sucks! BTW, I didn't take anything by modulo and I declared hash as integer not long long. Now I have only one question: why 5.000.000 pairs of integers eats ~40 MB memory(it's ok  each pair  (4B+4B) *5.000.000 ~ 40) BUT!!! why 5000 000 pairs of <long long,int> eats ~80MB?? I expected ( 8B(long long)+4B(int) )* 5.000.000 ~60MB!! very strange... Edited by author 07.11.2010 20:58 Edited by author 07.11.2010 20:58 It's due to data alignment. sizeof(pair<long long, int>) == 16. 8B(long long) + 4B(int) + 4B(unused).  Memory limit  Bogdan Holyshevskyi  1713. Key Substrings  15 Nov 2012 13:51  1  On submission 4620967 a have verdict MemoryLimit, but used memory is 8954KB.  Time limit exceeded  Mervin  1713. Key Substrings  24 Jul 2011 15:19  17  I find many solutions are less than 1 second. Could any one give me some hint to improve efficiency. Thanks in advance. I think that solutions which runs less than 1 sec. use hash table! How to construct Hash Table. If use substring of each command as the key, construction may consume too much time. to construct all substrings we need O(N*MaxLen^2) it is enough here! I solved it without hash table,that is why my solution works more than 1 sec. Edited by author 25.10.2009 00:35 What is mean of "MaxLen". Does it mean max command string length? oh If more than one command string have same substring. Do you consider it as same key value. Read statement! it is clear to understand it yourself! Thanks. Actually, I could not find clear connection between Hash Table and this problem. Look at previous post, there is another solution, without hash table! I am a new beginner on this website. Could I get algorithm rationale of solution posted by other programmers? if yes, How? How aboult test data. Where can I get? You could look at Statistics of each problem! You couldn't get test data. You could create your own, and somebody will answer on it! I would feel more appreciated if you could offer me some explanation or Reference Material. Thanks email: glbian@yahoo.com.cn MSN: glbian@live.com Thanks for your help. Interesting!? N*M*M~5 000 000 substring Let most of them are bad (or having equal copy). For equal string hash is equal and each bad substring must be compared at whole length ~ 50 with something. Thus we have 250 000 000 operations. I think that successful authors applied some string compressing. Hash with binary search  AC in 1.5 sec without wholelength comparing strings with equal hash  Tests  wRabbits_AlMag(VNTU)  1713. Key Substrings  22 Jul 2011 16:52  1  Tests wRabbits_AlMag(VNTU) 22 Jul 2011 16:52 2MB below memory limit =) Long live java Here some tests i used while debugging // TEST1 2 xex dex === xe d // TEST2 41 fambgpzqrty sdonrsdraukcyhuqkilkglngf sopodzkg bdcmwciyhndeglmlvqbqtthjryyuwgfclhjfip lbajgfskbozdqmgckgezznkpgugfz snsocdowvvqdev jksdqqenkgcqjthjzvojplfnugkdedrkc iqqpop ovpdvwfhfvolfxocniggdvjwrmx sja cobzqhaucqxswmwllshx lry oeiypcukxz lduqkoliyvcwnnbqugclobhjciikohxfoin hmz ojstdjsldeclaleqbfvhsadicrwkgqvzrmjhqhekxgvfd oufixbnpzoaayonlnslfkacqdjuiawoqfrkihabxgmsvgtcp ctlzhcmwejtadvuphcaspdvyf chhpnmm mrbtinhjnfolghxgdjidodstqkkfqogsbbpktlttghrepxjcol hfsjtscdjjlfdtfyegqvgteqzqmm nkrfvuqjahmmpmfazgsubmshituvypamhoj vksaiuuzs nbhuymzrmiuinaefhzfm dmwdvqmxqtiqybbfwf xeqnhxwfrhilciutjlpfoepaqemvpivkphwszacafleezx cjttarkxvfv vbc agevqmewepvrraktbgn lcxgjehoqexrenflpdoiptwqeruhtbiijmxrfqbxbxtl flcrqpdabhztdiykzvkbavrhxephdyhssjmhnrgvhoqzbm ggriibylnxqibmfpoqdiqjesqrtukvheib wfe icftkm gacivigsalt xmegpphjequeioughiqpznh mggtwlqcpdhsvovftb vsx fowgljhypolrqzmdzkpthinrvmapvbqhrrmbaodyikuuvnyqcx vgedqdhomtebcomvvkftuihtaihrubhawrs rsuahbpehidduujzpajshuugrpmzvd ==== ty cy sop bd lb sn jk iqq vw sja bz lry pc ko hmz ec uf ct ch mr ts kr uz uy dm qn cj vbc ag gj da ri fe cf ga xm lq vs lj om ua Edited by author 22.07.2011 16:55 

