Solved with Z-function in 17 rows of code (if don't count 10 rows for Z-function) 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. 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 WA 10 WA 14 bbaabb bbaabba Edited by author 30.07.2013 23:27 don't use hashes with modulo = 2^32, change it to 10^9 + 7 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 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.
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.
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). 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 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. 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 [code delete] Edited by author 09.05.2013 15:31 What the hell is test 9? In my computer I got 0.06s in worst case but still TLE 9! 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.. 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 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; } -------------------------------------------- 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 |
|