String can have size 1000, max size is not 999. longest palindromic substring is "kazak" itself. What am i missing ? It's case-sensitive. "Kazak" is not equal to "kazak"; 'K' is not equal to 'k' Help me please! looks like "aaaa" answer should be full string. input: aaaa output : aaaa #include <iostream> #include <string> #include<vector> using namespace std; string turn(string s) { string news; for (int i = s.length() - 1; i >= 0; i--) news.push_back(s[i]); return news; } int main() { string s; string news; getline(cin, s); vector <int> l; vector <string> counts; for (int i = 0; i < s.length(); i++) { int n = s.length(); for (int j = 1; j <= s.length() - n + 1 && (s.length() - n + 1) <= (s.length() - i); j++) { news = s.substr(i, j); if (turn(news) == news && news.length() > 1) { l.push_back(news.length()); counts.push_back(news); } n--; } } int maxl = 0; string saves; for (int k = 0; k < l.size(); k++) { if (l[k] > maxl) { maxl = l[k]; saves = counts[k]; } } cout << saves; } Try this simple test: 11123 Answer: 111 input : ABCDLKOIKJTFIDCBA ouput is a single letter such as A K and I NOT “ABCD” or what have you . Why is the answer not "ABCD" in this case? YES, why is not ABCD input : ABCDLKOIKJTFIDCBA oh...I see.. Edited by author 17.06.2016 15:54 I think ,cause we need to find a substring,not a subsequence Hi! I'm just amazed about this algorithm! My previous O(N^3) implementation take 0.624 and 508 KB with my best efforts to reduce runtime. When I submitted the Manacher's one, the runtime dropped down to 0.015 and 2376 KB!! Just google it. It's a very easy and efficient O(N) algorithm. That's all you need to solve this problem. No more than 30 lines of code. Do u give me your implemented solution? my cpp code is following: #include <cstdio> #include <algorithm> #include <cstring> #define fi first #define se second using namespace std; typedef long long LL; typedef pair<int, int> P; const int N = 5010, INF = 0x3f3f3f3f; int c[N], sa[N], x[N], y[N]; void GetSA(int *r, int *sa, int n, int m) { for (int i = 1; i <= m; i++) c[i] = 0; for (int i = 1; i <= n; i++) c[x[i] = r[i]]++; for (int i = 2; i <= m; i++) c[i] += c[i - 1]; for (int i = n; i >= 1; i--) if (c[x[i]]) sa[c[x[i]]--] = i; for (int k = 1, p = 0; k <= n; k <<= 1, p = 0) { for (int i = n - k + 1; i <= n; i++) y[++p] = i; for (int i = 1; i <= n; i++) if (sa[i] > k) y[++p] = sa[i] - k; for (int i = 1; i <= m; i++) c[i] = 0; for (int i = 1; i <= n; i++) c[x[i]]++; for (int i = 2; i <= m; i++) c[i] += c[i - 1]; for (int i = n; i >= 1; i--) sa[c[x[y[i]]]--] = y[i], y[i] = 0; swap(x, y); x[sa[1]] = p = 1; for (int i = 2; i <= n; i++) x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? p : ++p; if (p == n) break; m = p; } } int hei[N], rnk[N]; void GetH(int *r, int *sa, int n) { for (int i = 1; i <= n; i++) rnk[sa[i]] = i; for (int i = 1, k = 0, j; i <= n; hei[rnk[i++]] = k) for (k ? k-- : 0, j = sa[rnk[i] - 1]; r[i + k] == r[j + k]; k++); } int n; int s[N]; char str[N]; bool check(int a, int b, int len) { return n - a + 2 == b + len; } int main() { int mx = 0; scanf("%s", str + 1); int len = strlen(str + 1); for (int i = 1; i <= len; i++) s[i] = str[i], mx = max(mx, s[i]); s[len + 1] = '$'; for (int i = len; i >= 1; i--) s[len * 2 - i + 2] = str[i]; n = (len << 1) + 1; GetSA(s, sa, n, 1000); GetH(s, sa, n); P ans = P(1, -1); for (int i = 3; i <= n; i++) { int a = max(sa[i - 1], sa[i]), b = min(sa[i - 1], sa[i]); if (!(a > len + 1 && b <= len)) continue; if (check(a, b, hei[i]) && P(hei[i], -b) > ans) ans = P(hei[i], -b); } int pos = -ans.se; for (int i = pos; i < pos + ans.fi; i++) printf("%c", str[i]); puts(""); return 0; } I've tried to enlarge the alphabet size, but there's no effect. I also test lots of random test cases, all of them are correct. I hope someone could give me a hack data. Edited by author 21.02.2019 15:57 All right, I knew what's wrong... can you tell me why you wrong? i wrong on #27 too Test: ABBCC Answer: BB It's not that test( I have WA#17 but my prog writes "BB" on this test I had WA on this test. I used manacher algorithm from e-maxx, in realization on site is one mistake, what ruin solution on this test, after correcting i got AC 'qwerSOMETEXTrewq' isn`t 19 test. I got WA10 and my program was printing TEXT as my if condition was wrong at one place. I believe this is the test case for 10 as i got AC after fixing this. Thanks for that :) Hey, i seemed to have failed at Test 10 > <, with the input as "qwerSOMETEXTrewq", the output i get is qwer, which is right isn't it ? it should be "ETE",because "qwer" and "rewq" are separated Hi, everyone! I used Manacher's algorithm to solve this problem, but I got WA on #14 test. Can someone hint me, what could be the problem? It could be buggy implementation If just want to solve then you could do it with native algorithm, time limit is enough even for python Mahilewets Nikita, thanks you for your answer! I thought about the native solution already, but I want to solve it with Manacher's algorithm only. It is needed for increasing of my skills :) If someone has 14th test post it, please! OMG, I found my mistake :) This test was useful to me: 'babadada'. Right answer is 'adada' (not 'abada'). P.s. There is same problem at Codeleet. You may peek some test there :) Also my implementation of Manacher failed at test 5 And I decided to use naive My code in python 3.6: def is_palindrom(x): if x==x[::-1]: return True return False s=input() s=s[::-1] n=len(s) a=[] for x in range(2,n+1): for i in range(0,n-x+1): if is_palindrom(s[i:i+x]): a.append(s[i:i+x]) if len(a)==0: b=s[-1] else: b=a[-1] print(b) Memory is 70160 Kb, where so much it? Please, help, I would be grateful! I see you AC now What was the issue? Oh, sorry, it is other task I was so upset that I wa on #7 more than 10. I want to practice my suffix array,so I used it and used RMQ,But I wa on #7. I very want to know what is #7. Can the admin give the simple to me? thanks a lot http://paste.ubuntu.com/23169621/the suffix array algorithm is right cause I got AC ever using this Template~~ I got ac now cause I use a character '$' to end my suffix array . I think is ok but got wa on 7..why? Latin alphabet letters is not abcdefg.....ABCDGEF...? no no no . cause my book[] is smaller. book[500 + 20] is not enough? I see . the length of string is 2000 Edited by author 12.09.2016 21:19 tried all mentioned test cases .all correct. still WA on #12. using surfix array.any idea? code here: #include <cstdio> #include <cstring> int const N=220000; int st[256], rank[2*N], rank1[2*N], count[N], tmp[N]; char a[N], b[N], s[N], max1; int sa[N], height[N], si; int main(){ memset(st, 0, sizeof st); memset(rank, 0, sizeof rank); memset(rank1, 0, sizeof rank1); scanf("%s", b); int n1=strlen(b); for(int i=1; i<=n1; ++i)a[i]=b[i-1]; for(int i=1; i<=n1; ++i)a[i+n1+1]=b[n1-i]; a[0]=' '; a[n1+1]='#'; int n=2*n1+1; a[n+1]='&'; for(int i=1; i<=n; ++i)st[a[i]]=1; for(int i=1; i<=255; ++i)st[i]+=st[i-1]; for(int i=1; i<=n; ++i)rank[i]=st[a[i]];
int k=0; for(int p=1; k!=n; p+=p){ memset(count, 0, sizeof count); for(int i=1; i<=n; ++i)count[rank[i+p]]++; for(int i=1; i<=n; ++i)count[i]+=count[i-1]; for(int i=n; i>=1; --i)tmp[count[rank[i+p]]--]=i;
memset(count, 0, sizeof count); for(int i=1; i<=n; ++i)count[rank[i]]++; for(int i=1; i<=n; ++i)count[i]+=count[i-1]; for(int i=n; i>=1; --i)sa[count[rank[tmp[i]]]--]=tmp[i];
memcpy(rank1, rank, sizeof rank1); rank[sa[1]]=k=1; for(int i=2; i<=n; ++i){ if(rank1[sa[i]]!=rank1[sa[i-1]] or rank1[sa[i]+p]!=rank1[sa[i-1]+p])++k; rank[sa[i]]=k; } } k=0; for(int i=1; i<=n; ++i){ if(rank[i]==1){ k=0; }else{ --k; if(k<0)k=0; while(a[i+k]==a[sa[rank[i]-1]+k])++k; } height[rank[i]]=k; }
int max=-1; for(int i=2; i<=n; ++i){ int p=sa[i]; int q=sa[i-1]; if((p-1)/n1 != (q-1)/n1){ if(p+q+height[i]==n+2){ if(height[i]>max){ max=height[i]; si=p; } } } } for(int i=si; i<si+max; ++i)printf("%c", a[i]); return 0; } THX :) Are interesting in solving the task or in solving the task with suffix array or in knowing why your program outputs wrong at #12? Probably third is the case... So I tried to read your program. Have not understand. Maybe you elaborate details of your algorithm. You need to output the first of them if there are several such strings.But when you correct it ,i guess you 'll WA #18 My Code perfect AC with Visual Studio 2013, G++ 4.9, G++ 4.9 C++11. But Clang 3.5 gives output limit exceeded, or access violation.... Submit codes 7217044 7217043 |
|