c# - Longest Unique Palindromes -


i have following interface

public interface ipalindromeengine {     palindrome getlongestpalindrome(string sequence);      task<palindrome> getlongestpalindromeasync(string sequence);      list<palindrome> getlongestpalindromes(string sequence, int n, bool uniqueonly);      task<list<palindrome>> getlongestpalindromesasync(string sequence, int n, bool uniqueonly); }

with implementation taken http://www.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html code seems tested (from commenters , implementers)...

/// <summary> /// computes longest palindromic substring in linear time /// using manacher's algorithm. /// /// code lifted following excellent reference /// http://www.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html /// </summary> public class manacherpalindromeengine : ipalindromeengine {     // p[i] = length of longest palindromic substring of transform, centered @ i.     private int[] p;     private char[] transform;     private string sequence;      private void initialize()     {         transform = new char[sequence.length * 2 + 3];         transform[0] = '$';         transform[sequence.length * 2 + 2] = '@';         (int = 0; < sequence.length; ++i)         {             transform[2 * + 1] = '#';             transform[2 * + 2] = sequence[i];         }         transform[sequence.length * 2 + 1] = '#';     }      private void extractpalindromesviamanacher(string sequence)     {         this.sequence = sequence;         initialize();          int center = 0, right = 0;         p = new int[transform.length];         (int = 1; < transform.length - 1; i++)         {             int mirror = 2 * center - i;              if (right > i)                 p[i] = math.min(right - i, p[mirror]);              // attempt expand palindrome centered @ i.             while (transform[i + (1 + p[i])] == transform[i - (1 + p[i])])                 p[i]++;              // if palindrome centered @ expands past right,             // adjust center based on expanded palindrome.             if (i + p[i] > right)             {                 center = i;                 right = + p[i];             }         }     }      public palindrome getlongestpalindrome(string sequence)     {         if (string.isnullorempty(sequence))             return null;          extractpalindromesviamanacher(sequence);          int length = 0;         int center = 0;         (int = 1; < p.length - 1; ++i)         {             if (p[i] > length)             {                 length = p[i];                 center = i;             }         }         int startindex = (center - 1 - length) / 2;         string s = this.sequence.substring(startindex, length);         return new palindrome(s, startindex);     }      public task<palindrome> getlongestpalindromeasync(string sequence)     {         return task.run(() => getlongestpalindrome(sequence));     }      public list<palindrome> getlongestpalindromes(string sequence, int n, bool uniqueonly)     {         if (string.isnullorempty(sequence))             return null;          extractpalindromesviamanacher(sequence);          list<palindrome> palindromes = null;         if (uniqueonly)         {             palindromes = p                 .select((l, i) => new { length = l, index = })                 .orderbydescending(c => c.length)                 .select(c =>                 {                     int startindex = (c.index - 1 - c.length) / 2;                     string s = this.sequence.substring(startindex, c.length);                     trace.writeline(startindex);                     return new palindrome(s, startindex);                 })                 .tolist();             palindromes = palindromes                 .distinct(new palindrome.duplicatecomparer())                 .take(n)                 .tolist();         }         else         {             palindromes = p                 .select((l, i) => new { length = l, index = })                 .orderbydescending(c => c.length)                 .take(n)                 .select(c =>                 {                     int startindex = (c.index - 1 - c.length) / 2;                     string s = this.sequence.substring(startindex, c.length);                     trace.writeline(startindex);                     return new palindrome(s, startindex);                 })                 .tolist();         }         return palindromes;     }      public task<list<palindrome>> getlongestpalindromesasync(string sequence, int n, bool uniqueonly)     {         return task.run(() => getlongestpalindromes(sequence, n, uniqueonly));     } }

with 

public class palindrome {     public palindrome(string sequence, int startindex)     {         sequence = sequence;          if (startindex < 0)             throw new argumentexception("startindex must >= 0");         startindex = startindex;     }      public int startindex { get; set; }      public int length     {                 {             if (string.isnullorempty(sequence))                 return 0;             return sequence.length;         }     }      public string sequence { get; }      internal class duplicatecomparer : iequalitycomparer<palindrome>     {         public bool equals(palindrome x, palindrome y)         {             return x.sequence == y.sequence;         }          public int gethashcode(palindrome obj)         {             unchecked              {                 int hash = 17;                 return hash * 23 + obj.sequence.gethashcode();             }         }     } }

now have tested on number of test cases, 1 case not seem right. input string

"weeewweeew"

this returns results:

  1. weeewweeew start: 0 length: 10
  2. weeew start: 0 length: 5

  3. ee start: 1 length: 2

  4. why aren't getting string "eeewweee" or "eee"?

any other suggestions on code quality appreciated.

palindromes = p     .select((l, i) => new { length = l, index = })     .orderbydescending(c => c.length)

at point, every position in string, query contains length of longest palindrome centered @ position. in order retrieve all palindromes, need select of palindrome's substrings same center:

.selectmany(c => {     int startindex = (c.index - 1 - c.length) / 2;     int numsubpalindromes = (c.length + 1) / 2;     palindrome[] subpalindromes = new palindrome[numsubpalindromes];     (int = 0; < numsubpalindromes; ++i) {         string s = this.sequence.substring(startindex + i, c.length - * 2);         subpalindromes[i] = new palindrome(s, startindex + i);     }     return subpalindromes; }) .tolist();

Comments

Post a Comment

Popular posts from this blog

android - InAppBilling registering BroadcastReceiver in AndroidManifest -

i'm implementing inapp billing in android app. works well, however, i'm trying decouple broadcast receiver activity manifest. suggestion in android's trivialdrive sample: // important: dynamically register broadcast messages updated purchases. // register receiver here instead of <receiver> in manifest // because call getpurchases() @ startup, therefore can ignore // broadcasts sent while app isn't running. // note: registering listener in activity bad idea, done here // because sample. regardless, receiver must registered after // iabhelper setup, before first call getpurchases(). currently there's class extends broadcastreceiver : public class iabbroadcastreceiver extends broadcastreceiver { /** * intent action receiver should filter for. */ public static final string action = "com.android.vending.billing.purchases_updated"; private final iabbroadcastlistener mlistener; public iabbroadcastreceiver(iabbroadcastlistener listener) { m...
Read more

python Tkinter Capturing keyboard events save as one single string -

is possible store keyboard events 1 string? code below stores 1 char , prints it. card reader or bar code reader, contains collection of character/ string not 1 character @ time. goal save char pressed text variable. from tkinter import * root = tk() def key(event): text= event.char text+= event.char print ("pressed", text) def callback(event): frame.focus_set() print ("clicked at", event.x, event.y) frame = frame(root, width=100, height=100) frame.bind("<key>", key) frame.bind("<button-1>", callback) frame.pack() root.mainloop() currently, creating text variable , everytime key() function gets called, , text stores last character typed. you can define text module level variable , , use module level text inside key function - text = '' def key(event): global text text+= event.char print("pressed", text)
Read more

sql server - Why does Linq-to-SQL add unnecessary COUNT()? -

here tables: create table customer ( cid int primary key, name varchar(32) ) create table ord ( oid int primary key, cid int foreign key references customer, address varchar(20) ) here's linq-to-sql statement: var aaa = c in db.customer select new { c, o = c.ord.tolist() }; and here's inexplicable query generated linq-to-sql: select [t0].[cid] [cid], [t0].[name] [name], [t1].[oid] [oid], [t1].[cid] [cid2], [t1].[address] [address], (select count(*) [dbo].[ord] [t2] [t2].[cid] = [t0].[cid]) [value] [dbo].[customer] [t0] left outer join [dbo].[ord] [t1] on [t1].[cid] = [t0].[cid] order [t0].[cid], [t1].[oid] i want understand how rid of count(*) part. it's entirely uncalled for! linq needs count(*) in order determine number of entries returned o = c.ord.tolist() .
Read more