Show all threads Hide all threads Show all messages Hide all messages | Another approach | andreyDagger | 1684. Jack's Last Word | 22 Sep 2021 20:34 | 1 | Solved with Z-function in 17 rows of code (if don't count 10 rows for Z-function) | WA on TEST 20 | Ashiqur Rahman Nayeem | 1684. Jack's Last Word | 28 Mar 2020 04:35 | 2 | | Prefix definition | ghenady | 1684. Jack's Last Word | 21 Sep 2018 12:11 | 2 | For TC: abracadabra abrabracada why don't the prefixes are: abra abracada a? and also why for TC: abracadabra arbadacarba the prefix is not: a? why don't the prefixes are: abra abracada a? You can write this prefixes, this is the correct answer. why for TC: abracadabra arbadacarba the prefix is not: a? Because the word must consist entirely of prefixes. | KMP | Husayn Hasanov | 1684. Jack's Last Word | 29 May 2018 09:48 | 1 | KMP Husayn Hasanov 29 May 2018 09:48 | Random Test Cases | Aditya Singh | 1684. Jack's Last Word | 14 Nov 2017 17:28 | 1 | aaaaa aaa No aaa aaaaa aaaaaaaaa No aaaa aaaaa aabaa aabaabaabaaaaabaa No aab aab aaba aa aabaa aabaa aabaabaab No aab aab aab abcabcabccs abcaabcaabcaa No abca abca abca a aabaa aabaabaaaa No aab aabaa aa | give me some test, please !!! | Sunnat | 1684. Jack's Last Word | 6 Apr 2017 20:57 | 3 | bbaabb bbaabba Edited by author 30.07.2013 23:27 | for WA 26 | Arseny Babushkin (aytel)'` | 1684. Jack's Last Word | 17 Oct 2016 20:10 | 1 | for WA 26 Arseny Babushkin (aytel)'` 17 Oct 2016 20:10 don't use hashes with modulo = 2^32, change it to 10^9 + 7 | WA 3! | Felix_Mate | 1684. Jack's Last Word | 2 Jan 2016 14:59 | 1 | WA 3! Felix_Mate 2 Jan 2016 14:59 const Nmax=1000000; var s:array[0..Nmax-1] of char; z,ans,rans:array[0..Nmax-1] of longint; N,M,i,L,R,last,len:longint; ch:char;
function min(x,y:longint):longint; begin if(x>y) then x:=y; min:=x; end;
procedure Init; begin N:=-1; read(ch); while(ord(ch)>=ord('a'))and(ord(ch)<=ord('z')) do begin inc(N); s[N]:=ch; read(ch); end; readln;
inc(N); M:=0; s[N]:='#'; read(ch); while(ord(ch)>=ord('a'))and(ord(ch)<=ord('z')) do begin inc(N); inc(M); s[N]:=ch; read(ch); end; end;
BEGIN Init; z[0]:=N; L:=0; R:=0;
for i:=1 to N do begin if(i<=R) then z[i]:=min(z[i-l],R-i+1) else z[i]:=0; while(i+z[i]<=N)and(s[i+z[i]]=s[z[i]]) do inc(z[i]); if(i+z[i]-1>R)and(z[i]>0) then begin R:=i+z[i]-1; L:=i; end; end;
len:=0; last:=N; R:=0; i:=N; while(i>=N-M) do begin if(z[i]>=last-i+1) then begin inc(r); ans[r]:=i; rans[r]:=last; inc(len,last-i+1); last:=i-1; end; dec(i); end;
if(len<M) then writeln('Yes') else begin writeln('No'); for i:=r downto 1 do begin for l:=ans[i] to rans[i] do write(s[l]); write(' '); end; end; END. В чём баг хз.Уже сколько пытаюсь сдать-всегда WA3! Решал так:s1 и s2-входные строки,создаю строку s1#s2,вычисляю z-функцию для s=s1#s2,иду с конца строки до символа # и пытаюсь "покрыть" "не покрытые" символы. Если всю строку покрыл,то ответ No,иначе Yes | WA 3! HELP!!!! | Felix_Mate | 1684. Jack's Last Word | 28 Nov 2015 16:17 | 1 | Code: const Nmax=155000; var Z,L1,R1:array[1..Nmax] of longint; A:array[1..Nmax] of char; N,M,Middle,L,R,i,j,k:longint; ch:char;
function Min(x,y:longint):longint; begin if(x>y) then x:=y; Min:=x; end;
BEGIN N:=0; read(ch); while(ord(ch)>=ord('a')) do begin inc(N); A[N]:=ch; read(ch); end; readln;
inc(N); A[N]:='#'; M:=N; read(ch); while(ord(ch)>=ord('a')) do begin inc(N); A[N]:=ch; read(ch); end;
Z[1]:=N; R:=0; L:=0;
for i:=2 to N do begin if(i<=r) then Z[i]:=min(R-i+1,Z[i-L+1]) else Z[i]:=0; while(i+z[i]<=N)and(A[i+z[i]]=A[z[i]+1]) do inc(z[i]); if(i+z[i]-1>r) then begin L:=i; R:=i+z[i]-1; end; end;
k:=0; L1[k]:=N+1; R1[k]:=N+1;
i:=N; while(i>=M+1) do begin if(i+z[i]-1>=L1[k]-1) then begin inc(k); L1[k]:=i; R1[k]:=L1[k-1]-1; end; dec(i); end;
if(L1[k]=M+1) then begin writeln('No'); while(k>0) do begin for i:=L1[k] to R1[k] do write(A[i]);write(' '); dec(k); end; end else begin writeln('Yes'); end; END.
| WA 1!!! HEEEEEEEELP!!! | Felix_Mate | 1684. Jack's Last Word | 13 Jul 2015 18:59 | 1 | I can't find any error. My program solve all tests,my I got WA1!!! My code: var Z:array[1..151000] of longint; A,C:array[1..151000] of char; N,L,R,i,j,k,ind,M,t:longint; ch:char; find:boolean;
function Min(x,y:longint):longint; begin if(x>y) then x:=y; Min:=x; end;
BEGIN N:=0;
ch:='a'; while(ord(ch)>50) do begin read(ch); if(ord(ch)>50) then begin inc(N); A[N]:=ch; end; end;
A[N+1]:='+'; ind:=N+1; inc(N); readln;
ch:='a'; while(ord(ch)>50) do begin read(ch); if(ord(ch)>50) then begin inc(N); A[N]:=ch; end; end;
Z[1]:=N; R:=0; L:=0;
for i:=2 to N do begin if(i<=r) then Z[i]:=min(R-i+1,Z[i-L+1]) else Z[i]:=0; while(i+z[i]<=N)and(A[i+z[i]]=A[z[i]+1]) do inc(z[i]); if(i+z[i]-1>r) then begin L:=i; R:=i+z[i]-1; end; end;
find:=true; i:=N; while(i>=ind+1) do begin k:=i; while(i>=ind+1)and(Z[i]<k-i+1) do dec(i); if(i<ind+1) then find:=false; dec(i); end;
if(find) then begin writeln('No '); i:=N; M:=1; while(i>=ind+1) do begin k:=i; while(i>=ind+1)and(Z[i]<k-i+1) do dec(i); t:=M; for j:=k downto i do begin C[t]:=A[j]; inc(t); end; C[t+1]:=' '; M:=t+2; dec(i); end;
for i:=M-2 downto 1 do begin write(C[i]); end; end else begin write('Yes'); end; END.
| a test case for WA#4 | jieshuzheng | 1684. Jack's Last Word | 27 Nov 2014 22:11 | 2 | ababa ababab if you use kmp, you should pay attention when your index for the first word round up. It takes hours to find the problem. As to me, the problem was with special symbols. In this test end of the first line was defined by two symbols (like Windows style: 10 and 13). | Output Limit Exceeded | AlexDevyatov | 1684. Jack's Last Word | 9 Jul 2014 23:08 | 1 | Why OLE 24? #pragma comment(linker, "/STACK:64777216") #define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<stdio.h> #include<algorithm> #include<vector> #include<math.h> #include<string> #include<sstream> #include<set> #include<map> #include<stack> #include<queue> #include<deque> #include<memory.h> #include<ctime> #include<cassert> #define pb push_back #define sz(a) (int)a.size() #define bs binary_search #define np next_permutation #define mp make_pair #define all(a) a.begin(),a.end() #define read(a) scanf("%d", &a) #define writeln(a) printf("%d\n", a); #define forn(i, n) for (int i = 0; i < n; ++i) #define forv(i, v) for (int i = 0; i < sz(v); ++i) #define _(a, b) memset(a, b, sizeof a) typedef long long ll; typedef unsigned long long ull; using namespace std; template<class T> inline T sqr(T x) { return x * x; } const double pi = acos(-1.0), eps = 1e-18; const int INF = 1000 * 1000 * 1000, MAXN = 100005, MOD = INF + 7; string s, t, ls, ans = ""; int kmp[75000 * 2 + 5]; vector<int> pos; char al[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'}; void prepare(string s) { #ifdef _DEBUG freopen("input.txt", "r", stdin); freopen("output.txt","w",stdout); #else if (sz(s) != 0) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); } #endif } void gen () { srand(time(NULL)); string TMP = ""; forn (i, 70000) { int k = rand() % 8; cout << al[k]; TMP += al[k]; } cout << '\n'; cout << TMP; } void solve() { cin >> s >> t; ls = s + "*" + t; kmp[0] = 0; for (int i = 1; i < sz(ls); i++) { int k = kmp[i-1]; while (k > 0 && ls[i] != ls[k]) { k = kmp[k-1]; } if (ls[i] == ls[k]) ++k; kmp[i] = k; } for (int i = sz(s) + 1; i < sz(ls); i++) { if (kmp[i] == 0) { cout << "Yes"; return; } if (i != sz(s) + 1 && kmp[i] <= kmp[i-1]) pos.pb(kmp[i - kmp[i]]); } pos.pb(kmp[sz(ls)-1]); cout << "No\n"; string tmp = ""; int cnt = 0; forn (i, sz(pos)) { bool f = false; cnt += pos[i]; forn (j, pos[i]) { cout << s[j]; f = true; } if (i != sz(pos) - 1 && pos[i]) cout << " "; } } int main() { prepare(""); //gen(); solve(); return 0; } Edited by author 09.07.2014 23:18 | For everyone who thinks that his solution( C++ ) is correct, but has TLE.. | PersonalJesus | 1684. Jack's Last Word | 30 Jan 2014 23:22 | 5 | Do NOT use STL's strings, use standart C char arrays instead. That makes a HUGE difference in the time and memory complexity. I hope that this will be helpful to somebody:) i disagree, my solution takes 0.046 seconds... and i use string, vector Do NOT use STL's strings, use standart C char arrays instead. That makes a HUGE difference in the time and memory complexity. I hope that this will be helpful to somebody:) STL string - TL 12, 10 MB used. Char arrays - AC 0.031, 1.24 MB used... I got TLE. But after changing "s1.size()" on "long ns1 = s1.size()" and "s2.size()" on "long ns2" got AC. =) And I changed "vector" on "deque"( for deleting elements from begining ). Edited by author 14.12.2011 16:27 Edited by author 14.12.2011 16:30 Got 0.062 and 1485 KB with pure STL and strings: just start your program with cin.sync_with_stdio(false); Btw, to get a O(n) solution consider that if a suffix of the last word is a prefix of the first word (check thru hash), then it is safe to assume that this suffix is in the answer. | A test may be help you get AC! | yuyan | 1684. Jack's Last Word | 28 Dec 2013 05:28 | 3 | abcd aaaa The answer is obvious. Good luck! Thank you! This test is helpful for wa#5. Answer: No a a a a PS.: but for my program this answer is not obvious. =) Edited by Trolol 14.12.2011 15:49 Edited by author 14.12.2011 15:50 thanks a lot! wa5 is fixed | WA 10 | Sunnat | 1684. Jack's Last Word | 3 May 2013 15:20 | 1 | WA 10 Sunnat 3 May 2013 15:20 [code delete] Edited by author 09.05.2013 15:31 | TLE 9 | Facundo | 1684. Jack's Last Word | 19 Apr 2013 20:56 | 1 | TLE 9 Facundo 19 Apr 2013 20:56 What the hell is test 9? In my computer I got 0.06s in worst case but still TLE 9! | Help plz | ACSpeed - Nguyen Khac Tung | 1684. Jack's Last Word | 7 Oct 2012 20:55 | 2 | Help plz ACSpeed - Nguyen Khac Tung 30 Jan 2012 16:06 abracadabra arbadacarba In example 2 , why is this answer wrong : NO a r b a d a c a r b a All of them are "its nonempty prefix" ? All of them should be "non-empty" and "prefix" ... well in ur case "r" itself is not a prefix so ..this is WA hope this explains and helps.. | Why not "abra bra cada" | Kumaar | 1684. Jack's Last Word | 7 Oct 2012 19:37 | 4 | Even this answer is ok right? because 'bra' isn't prefix WA #3 please suggest I do not have to take 1st string's legth in consideration... I am doing kmp failure function tabulation... for suffix match of string b with prefixes of a and thus ... only b's string length is taken care of .... plz suggest some test case where I might be wrong.. what m doing is this -------------------------- // n is the string length of b f.resize(n+2); f[0]=-1; int x; for(int i=1;i<=n;i++) { x=f[i-1]; while(x>=0&&a[x+1]!=b[i-1]) x=f[x]; if(a[x+1]==b[i-1]) f[i]=x+1; else f[i]=-1; } -------------------------------------------- Edited by author 07.10.2012 20:52 | If you have WA#3 | bsu.mmf.team | 1684. Jack's Last Word | 7 Oct 2012 19:33 | 2 | Pay attention to the fact that sizes of strings may distinguish. I do not have to take 1st string's legth in consideration... I am doing kmp failure function tabulation... for suffix match of string b with prefixes of a and thus ... only b's string length is taken care of .... plz suggest some test case where I might be wrong.. what m doing is this -------------------------- // n is the string length of b f.resize(n+2); f[0]=-1; int x; for(int i=1;i<=n;i++) { x=f[i-1]; while(x>=0&&a[x+1]!=b[i-1]) x=f[x]; if(a[x+1]==b[i-1]) f[i]=x+1; else f[i]=-1; } -------------------------------------------- | Test | nobik | 1684. Jack's Last Word | 22 Jun 2012 15:46 | 1 | Test nobik 22 Jun 2012 15:46 abcd aaaaabcdaaaa ans : a a a a abcd a a a a When I print answers,I print them from the end))) Sorry for my poor English)))) Edited by author 22.06.2012 15:47 |
|
|