|
|
Страница 2 Using the same code, and only switching the order of the 2 input strings ... scanf("%s", strr); scanf("%s", strl); leads to WA5 switching the order (shouldn`t make any difference) scanf("%s", strl); scanf("%s", strr); and I get WA6 Plz help me, I used hashing with binary search and got WA on 52. There was the same problem. The reason is a hash collision. Try a double hash (with two modules) Страница 1 use N = 100001 instead N = 100000 I have got a verdict Compiler Failed on Clang compiler. Never have got such a verdict. Every other compiler submit gets AC. Can't post code here because it is a working solution. So at first I got AC in 68 ms using scanf("%c", *char) and then I replaced scanf with_getchar_nolock() and got AC in 46 ms... And 31 ms with _putchar_nolock! Edited by author 16.09.2015 13:22 my solution WA7, anyone post more test? thanks! my solution WA7, anyone post more test? thanks! i tried to solve this problem with dp. O(N*2) time and O(N) memory: here is my code #include<iostream> #include<string> #include<vector> #include<algorithm> using namespace std; int n; string s,t; string Longest_common_substr(void) { int place; int longest=0; vector<int> m(n); for(int i=0;i<n;i++) { for(int j=n-1;j>=0;j--) { if(s[j]==t[i]) { if(j!=0)m[j]=m[j-1]+1; else m[j]=1; } else m[j]=0; if(m[j]>longest) { longest=m[j]; place=j-longest+1; } if(longest==n)return s.substr(place,longest); } } if(longest==0)return ""; else return s.substr(place,longest); } int main() { ios::sync_with_stdio(0); cin.tie(); cin>>n; cin>>s; cin>>t; cout<<Longest_common_substr()<<endl; return 0; } can you please suggest any modifications? It seems that lots of people can solve this problem with hashing. Well, I'm using 64 bit hashing and am using sufficiently large prime p (I'm using the usual polynomial hashing i.e. s[0]+s[1]*p+s[2]*p*p ...). I have tried 5 different p's and I'm always catching collisions at test 52 !!! I added code to check for collision and keep working with a different random chosen p ... and now I get TL !!! My question is: what is the smart solution to the problem that I have? What hashing have you used? To admins: How can you guys make solutions with random p get collisions? That's probably a really good test. I know how to build anti-hash for certain p, but I cannot imagine a test that hacks 10 random p's in a row. Good job! Or more like "my solution sucks" :) QProgS 1517. Свобода выбора Visual C++ 2010 Accepted 0.656 9 720 КБ Accepted with double hashing ) Edited by author 23.11.2013 18:01 [code deleted] ------------------------------------------------------------------------------------- I've got AC. If you wa on test#3 , you should wirte your OWN suffix array base on your UNDERSTANDING cause it's too easy . If you want my help , just send me an e-mail . adress : ngziming@gmail.com . ------------------------------------------------------------------------------------- pleased try this data input: 5 CCCCC CCCCC output: CCCCC ------------------------------------------------------------------------------------- hint: remeber to add a no-use char at the last of the string . ------------------------------------------------------------------------------------- Edited by author 16.08.2012 09:29 Some new tests were added. 127 authors lost their AC. Теперь из-за антихеш тестов все задачи перерешивать? Спасибо :) Всегда пожалуйста. Очередной реджадж уже в процессе. Suffix Array Without Longest Common Prefix O(N*logN) 0.312 Edited by author 31.01.2014 21:34 Antihash tests are дрочерство. Does anyone see what goes wrong with my program for the input of test #9? or test inputs maybe? EDIT: Test Case found! Edited by author 01.06.2012 22:08 Can you tell me how to fix WA 9, plz my algo Accepted in 0.4s. Edited by author 23.05.2012 16:24 17 WEARECHAMPIONSYES WEHAVECHAMPIONSNO What should I write in this case ??? Sory my english Edited by author 10.04.2011 23:15 Edited by author 10.04.2011 23:16 You should output empty string. You can't solve this problem without paznavania, this is an unic method of solving. This method was created in the 12 century, by Greece phylosofers, but unfortunately, is destroied now, because Greece enemies destroies it. But there are legends that some nations stole the method of paznavania and I surely know that who solved this problem is a representative of that nation who stole, because, as you know, without paznavania this problem couldn't be solved... :(((( Edited by author 17.02.2008 00:48 Yes,I think that you are right,but I think that you were not right in the afternoon
Edited by author 17.02.2008 00:22 I agree with you, but I see that you don't know the history of this method very well. Method "Paznavania" is the result of developing of method "Dazozorivanie", which was created in ancient times and later, step-by-step it reached it's highest perfection and was given a new name "paznavanie"(by its developer Numanchik Paznavaius). I tried to test method "dozozorivanie" but unfortunately there is time limit problem:( so "paznavanie" is the one method to solve this problem. Edited by author 17.02.2008 00:55 |
|
|