SPOJ::LCS2 - Longest Common Substring II

LCS2 problem can be solved by using SuffixAutomata a.k.a DAWG. I have written a small writeup on DAWGshere. I suggest you to go through it, if you are not comfortable with DAWGs.

// =====================================================================================
//    Description:
//         Author:  BrOkEN@!
// =====================================================================================
 
#include<fstream>
#include<iostream>
#include<sstream>
#include<bitset>
#include<deque>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<algorithm>
#include<iterator>
#include<string>
#include<cassert>
#include<cctype>
#include<climits>
#include<cmath>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
 
using namespace std;
 
template< class T > inline T _maxOfThree(T a,T b,T c) {return max(max(a,b),c);}
template< class T > inline T _abs(T n) { return (n < 0 ? -n : n); }
template< class T > T _square(T x) { return x * x; }
template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a%b) : a); }
template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); }
template< class T > bool in_range(T x, T i, T y) { return x<=i && i<=y; }
 
 
#define FOR(i,a,b) for(typeof((a)) i=(a); i <= (b) ; ++i)
#define REV_FOR(i,a,b) for(typeof((a)) i=(a); i >= (b) ; --i)
#define FOREACH(it,x) for(typeof((x).begin()) it=(x).begin(); it != (x).end() ; ++it)
#define REV_FOREACH(it,x) for(typeof((x).rbegin()) it=(x).rbegin(); it != (x).rend() ; ++it)
#define SET(p, v) memset(p, v, sizeof(p))
#define CPY(p, v) memcpy(p, v, sizeof(p))
#define CLR(p) SET(p,0)
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define ARRAY_SIZE(array) (sizeof(array) / sizeof((array)[0]))
#define __int64 long long
 
typedef pair<int,int> PI;
typedef vector<PI> VI;
 
const int ALPHA_MAX = 26;
const int MAX = 201000;
 
typedef struct state{
    int length;
    state* link;
    state* next[ALPHA_MAX];
    int lcs,nlcs;
} state;
 
 
    int total=0;
    state pool[MAX<<1];
    state* tpool[MAX<<1];
    int counts[MAX];
   
    state* head;
    state* last;
   
    void sam_init(){
        head=last=&pool[total++];
    }
   
    void sam_track(int length){
        for(int i=0;i<total;i++) counts[pool[i].length]++; 
        for(int i=1;i<=length;i++) counts[i]+=counts[i-1]; 
        for(int i=0;i<total;i++) {    tpool[--counts[pool[i].length]]=&pool[i]; }
    }
   
    void sam_updateBests(){
        state* p=NULL;
        for(int i=total-1;i>=0;i--) {
            p=tpool[i];
            if(p->lcs<p->nlcs) p->nlcs = p->lcs;
            if(p->link && p->link->lcs<p->lcs) p->link->lcs = p->lcs;
            p->lcs =0;
        }
    }
   
    int sam_best(){
        int ans=0; 
        for(int i=0;i<total;i++) if(pool[i].nlcs>ans) ans=pool[i].nlcs;
        return ans;
    }
   
    void sam_insert(int ch,int len){
        state* curr = &pool[total++];
        curr->length = curr->nlcs = len;
       
        state* p = last;
        while(p && !p->next[ch]) p->next[ch]=curr,p=p->link;
        if(!p){
            curr->link = head;
        }else{
            state* q = p->next[ch];
           
            if(p->length +1 == q->length){
                curr->link = q;
            }else{
                state* clone = &pool[total++];
                *clone = *q; 
                clone->length = clone->nlcs = p->length +1;
               
                while(p && p->next[ch]==q) p->next[ch]=clone,p=p->link;
                curr->link = q->link = clone;
            }
        } 
        last = curr;
    }
   
    void sam_traverse(state** p,int& len,int ch){
        while(*p!=head && (*p)->next[ch]==NULL){
            *p = (*p)->link;
            len = (*p)->length;
        }
        if((*p)->next[ch]){
            *p = (*p)->next[ch];
            len++;
        }
        if(len > (*p)->lcs) (*p)->lcs = len;
    }
   
 
char A[MAX];
int lenA=0;
 
int lcs(){
    sam_init();
    scanf("%s",A);
    lenA = strlen(A);
    FOR(i,0,lenA-1) sam_insert(A[i]-'a',i+1);
    sam_track(strlen(A));
   
 
    while(scanf("%s",A)!=EOF){
     lenA = strlen(A);
        int l = 0;
        state* p = head;
        FOR(i,0,lenA-1){
            sam_traverse(&p,l,A[i]-'a');
        }
        sam_updateBests();
    }
    return sam_best();
}
 
int main(){
    printf("%d\n",lcs());
    return 0;
}

[Algorithms] Suffix Automata (DAWG)

KeyWords: string-matching, pattern-matching, indexing, inverted text, finite-automata, suffix-trees, suffix-automata,suffix-tries, factor-automata, music identification, Directed Acycle Word Graph (DAWG).

Let me name some common problems on string.

finding Least Common String of strings, Sub String search, Palindromes, Angarams, Dictionary search, Commonly occuring string (Atom String), unique significant substring/pattern, least common prefix, least common suffix, whats not in the list.

The key point for solving all of these problems is , maintain all data about a string.
All data about a string means {All prefix substrings,All suffix substrings, All sub-strings} .

What matters here ??

You can solve string related problems using, either Brute Force method or using some Data Structure which will allow you to store data about string, considering your time/space complexities.

    the way your data-structure stores data about  the string? -Time and space taken for processing of the string.
    the way your data-structure retrieves data about the string?- Query response time /time taken to retrieve the data.

If you are going to use data-structures, here are the few structure that you'll obvisouly look out for.



Data about strings can be comprised in either a Suffix-Tree/Trie or Suffx-Array or Finite-Automata or Factor-Oracle.

So many people did a vast research on the area of string processing.If this area interests you as well, then you should go throught the sources mentione at the end of this post.

Since, space-time are driving factors in dealing with large data, i prefer to construct a suffx automata(DAWG), for the problems on strings.

Examples of DAWGs:

For String ""

For String "a"

For String "aa"

For String "ab"

For String "aba"

For String "abb"

For String "abbb"

Explanation(Example String: "GCAGAGAG"):

State-3 is cloned as State-6 while inserting 2nd 'A', after state-4, to allow DAG Flow for the suffix string AGAGAG,AGXXXX
State-4 is cloned as State-8 while inserting 2nd 'G', after state-6, to allow DAG Flow for the suffix string GAGAG,GAXXX.
...Just do some work around on this string further, you will understand.

Constructing Suffix-Automata in O(N)-Time / O(N logK) space(Forward DAWG Matching algorithm):

Forward DAWG Matching algorithm, which is smallest suffix automation with Deterministic Finite Automaton.

How to Construct:
1. Define the state
    typedef struct state{
        int length;             //Length of the DAWG till this state
        state* prev;            //Link to previous transition state in the DAWG
        state* next[ALPHA_MAX]; //Links to next transition state in the DAWG
    } state;

2. Automata is constructed with set of states and transition from state-to-state. 
So define your Automata which comprises of the states, variables to track states and methods that enables to do state transitions.
    typedef struct SAM{
        /*FSM Variables*/
        state pool[MAX];        //You need a pool of states, from where you can pick a raw state to include in the DAWG.    
        int count;              //You need to track number of states present in the DAWG.
        state* head,last;       //You need to track your head of the DAWG and last State of the DAWG.

        /*FSM Methods*/
        void SAM_init();            //Initialize your Finite state Machine.
        voidSAM_extend(int input);  //Based on the  input extend states in your FSM(Finite State Machine)
    } SAM;

3. Initialization of FSM.
    void SAM::SAM_init(){
            memset(pool,0,sizeof(pool));
            count=0;
            head=last=&pool[count++];
    }

4. Extending the FSM.
    void SAM::SAM_extend(int input){
        state* new_state = &pool[count++];
        new_state->length = 1 + last->length;
        state* p = last;
        for( ; p && !p->next[input]; p->next[input]=new_state,p=p->prev);
        if(!p){
            new_state->prev = head;
        }else{
            state* q = p->next[input];
            if(p->length +1 == q->length){
                new_state->prev = q;
            }else{
                state* clone = &pool[total++];
                *clone = *q;
                clone->length = p->length +1;
                for(;p && p->next[input]==q;p->next[input]=clone,p=p->prev);
                new_state->prev = q->prev = clone;
            }
        }
        last = new_state;
    }

5. You can include other methods, If required (like below method, which i used it for the traversal of the DAWG.)
    void SAM::SAM_traverse(state** p,int& len,int input){
        while(*p!=head && !(*p)->next[input]){
            *p = (*p)->link;
            len = (*p)->length;
        }
        if((*p)->next[input]){
            *p = (*p)->next[input];
            len++;
        }
    }

Sources:
http://www.cs.nyu.edu/~mohri/pub/nfac.pdf
http://cbse.soe.ucsc.edu/sites/default/files/smallest_automaton1985.pdf
http://www-igm.univ-mlv.fr/~lecroq/string/fdm.html#SECTION00220
http://e-maxx.ru/algo/suffix_automata
http://www-igm.univ-mlv.fr/~lecroq/string/node1.html

Practise problems:
http://www.spoj.com/problems/LCS/
http://www.spoj.com/problems/LCS2/

SPOJ-2916::Can you answer these queries V

http://www.spoj.com/problems/GSS5/

Typical problem statement can be seen as below.

Problem: Given a array of numbers a[1...n] , and a Query(x1,y1,x2,y2).
Query(x1,y1,x2,y2) = Max { A[i]+A[i+1]+...+A[j] ; x1 <= i <= y1 , x2 j <= y2 and x1 <= x2 , y1 <= y2 }.

Lets analyze this query...
Wait a minute...!!
    Have you read my post on GSS1 problem ??
    Have you ever Solved GSS1 problem ??
If your answer is NO, then I suggest you to do that problem first.
http://code.karumanchi.me/2013/07/spoj-1043can-you-answer-these-queries-i.html


Here two cases araises based on {x1 <= i <= y1 , x2 j <= y2 and x1 <= x2 , y1 <= y2 }.
 Case-1: (x1,y1) and (x2,y2) doesn't overlap.
 Case-2: (x1,y1) and (x2,y2) overlaps.

Case-1::No Overlapping
 result would be (x1,y1).bestRightSum + (y1+1,x2-1).Sum +(x2,y2).bestLeftSum;

Case-2::No Overlapping
 result would be max of
   {
   (x1,x2-1).bestRightSum  + (x2,y2).bestLeftSum,
   (x1,y1).bestRightSum  + (y1+1,y2).bestLeftSum,
   (x2,y1).bestSum
   }




Implementation of the Same - Solution

// =====================================================================================
//       Filename:  GSS5.cpp
//    Description:
//         Author:  BrOkEN@!
// =====================================================================================
#include<cassert>
#include<cctype>
#include<climits>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<bitset>
#include<deque>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<fstream>
#include<iostream>
#include<sstream>
#include<streambuf>
#include<algorithm>
#include<iterator>
#include<new>
#include<string>
#include<utility>

template< class T >
inline T maxOfThree(T a, T b, T c){
    return max(max(a,b),c);
}

#define FOR(i,a,b) for(typeof((a)) i = (a); i <= (b) ; ++i )
#define REV_FOR(i,b,a) for(typeof((b)) i = (b); i >= (a) ; --i )
#define FOREACH(it,x) for(typeof((x).begin()) it=((x).begin()); it != ((x).end()); ++it)
#define REV_FOREACH(it,x) for(typeof((x).rbegin()) it=((x).rbegin()); it != ((x).rend()); ++it)


using namespace std;

typedef pair<int,int> PI;
typedef vector<PI> VI;

typedef struct node{
    int bestLeftSum,bestRightSum,Sum,bestSum;
   
    node merge(node& l,node& r){
        bestLeftSum = max(l.bestLeftSum,l.Sum+r.bestLeftSum);
        bestRightSum = max(l.bestRightSum+r.Sum,r.bestRightSum);
        Sum = l.Sum + r.Sum;
        bestSum = maxOfThree(l.bestSum,r.bestSum,l.bestRightSum+r.bestLeftSum);
    }
   
    node setNode(int val){
        bestLeftSum = bestRightSum = Sum = bestSum = val;
    }
       
} node;


const int MAX = 1<<14;

node T[MAX<<1];
int A[MAX];

void init(int Node,int i,int j){
    if(i==j){
        T[Node].setNode(A[i]);
        return;
    }else{
        int m = (i+j)/2;
        init(2*Node,i,m);
        init(2*Node+1,m+1,j);
        T[Node].merge(T[2*Node],T[2*Node+1]);
    }
}

node range_query(int Node,int i,int j,int L,int R){
    if(L > R) return T[0];
    if(i==L && R==j){
        return T[Node];
    }else{
        int m = (i+j)/2;
        if(R<=m){
            return range_query(2*Node,i,m,L,R);
        }else if(L>m){
            return range_query(2*Node+1,m+1,j,L,R);
        }else{
            node resultNode,left,right;
            left = range_query(2*Node,i,m,L,m);
            right = range_query(2*Node+1,m+1,j,m+1,R);
            resultNode.merge(left,right);
            return resultNode;
        }
    }
}

int query(int N,int x1,int y1,int x2,int y2){
    int result =0;
    if(y1<x2){
        result += range_query(1,0,N-1,x1,y1).bestRightSum;
        result += range_query(1,0,N-1,y1+1,x2-1).Sum;
        result += range_query(1,0,N-1,x2,y2).bestLeftSum;
    }else{
        result += maxOfThree(
                    range_query(1,0,N-1,x1,x2-1).bestRightSum  + range_query(1,0,N-1,x2,y2).bestLeftSum,
                    range_query(1,0,N-1,x1,y1).bestRightSum  + range_query(1,0,N-1,y1+1,y2).bestLeftSum,
                    range_query(1,0,N-1,x2,y1).bestSum
                    );
           
    }
    return result;
}

int main(){
    int T=0;
    scanf("%d",&T);

    int N=0,Q=0,x1=0,y1=0,x2=0,y2=0;
    FOR(t,1,T){
        scanf("%d",&N);
        FOR(i,0,N-1){scanf("%d",&A[i]);}
        init(1,0,N-1);
        scanf("%d",&Q);
        FOR(q,1,Q){
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            --x1;--y1;--x2;--y2;
            printf("%d\n",query(N,x1,y1,x2,y2));
        }
    }

    return 0;
}

Google Code Jam 2012 - Qualification Round

Compared to my performance in 2011 Code Jam, this year I just turned out to be a big disaster.
Yes, and I found that its very hard to make my rusted brain to make it work on these awesome set of problems. Thank God the qualification cut-off was too low...so that Idiots like me also get into to Round-1 :P :P.

Problem 1 - Speaking in Tongues
I guess most of the people would have cracked it very easily and it was the same for me. Not much to think about the solution. Its just a Character Mapping from the input set. You will be able to map all 26-character very easily.

import java.util.Arrays;
import java.util.Scanner;

public class Problem1 {
 public static void main(String args[]){
  Scanner in= new Scanner(System.in);
  String Normal="abcdefghijklmnopqrstuvwxyz ";
  String Google="yhesocvxduiglbkrztnwjpfmaq ";
  String fline=in.nextLine();
  Scanner in1= new Scanner(fline);
  int T = in1.nextInt();
  for(int l=0;l<T;l++){
   StringBuffer G=new StringBuffer(in.nextLine());
   System.out.print("Case #"+(l+1)+": ");
   for(int i=0;i<G.length();i++){
    System.out.print(Google.charAt(Normal.indexOf(G.charAt(i))));
   }
   System.out.println();
  }
 }
}

Problem 3: Recycled Numbers
I thought it was a easy problem and I did solved the small input set. But the real problem was Large Input set and I made a big blunder in the computation.
I gave generic solution but never thought that the code would ditch me in large number range.After all i'm a bad coder. :P :P
This is what i've written for the small input set. There are better algorithms than what i've written here.
I could've avoided below silly mistakes. Anyways it saved me :D.
Didn't give much attention trailing 0's.
Computations take much time for Input range is large. I should've been little smart using the HashSet etc to get rid of duplicates.
I should've make use of the boundary conditions effectively.

import java.util.Scanner;

public class Problem3 {
 public static void main(String args[]){
  Scanner in= new Scanner(System.in);
  Scanner rin= new Scanner(in.nextLine());
  int T = rin.nextInt();
  for(int l=0;l<T;l++){
   rin= new Scanner(in.nextLine());
   int lower = rin.nextInt();
   int upper = rin.nextInt();
   int count=0;
   while(lower<upper){
    for(int m=lower+1;m<=upper;m++){
     if(isRecycledPair(lower,m)){
      count++;
     }
    }
    lower++;
   }
   System.out.println("Case #"+(l+1)+": "+count);
  }
  
 }
 
 static String rightRotateString(String str){
  char strC[]=str.toCharArray();
  int i=0;
  char temp=strC[strC.length-1];
  for(i=strC.length-1;i>0;i--){
   strC[i]=strC[i-1];
  }
  strC[i]=temp;
  return (new String(strC));
 }
 
 static boolean isRecycledPair(int n,int m){
  String nS=Integer.toString(n);
  String mS=Integer.toString(m);
  if(nS.matches(mS))
   return true;
  for(int i=0;i<nS.length()-1;i++){
   nS=rightRotateString(nS);
   if(nS.matches(mS)){
    return true;
   }
  }
  return false;
 }
}

This is one of the work arounds for the same. The logic simple. Take a each number in the range. find all the rotations of that string :D . and the pair is definately a ReCycled pair for god sake :P :P. But you need to take care of the duplicates if there are any, so HashSet ;).

import java.util.HashSet;
import java.util.Scanner;

public class Problem3 {
 public static void main(String args[]){
  Scanner in= new Scanner(System.in);
  Scanner rin= new Scanner(in.nextLine());
  int T = rin.nextInt();
  for(int t=1;t<=T;t++){
   rin= new Scanner(in.nextLine());
   System.out.println("Case #"+t+": "+getNumberOfPairs(rin.nextInt(),rin.nextInt()));
  }
 }
 
 private static int getNumberOfPairs(int A,int B){
  int count=0;
  HashSet<Integer> s = new HashSet<Integer>();
  for (int n = A; n < B; n++) {
   String i=Integer.toString(n);
   s.clear();
   int t = i.length();
   while(i.charAt(t-1)=='0')
    t--;
   for(int j=1;j<t;j++){
    int m= Integer.parseInt(i.substring(j)+i.substring(0,j));
    if(n<m && m<=B){
     s.add(m);
    }
   }
   count+=s.size();
  }
  return count;
 }
}

Problem 2: Dancing with Googlers
This is one of the good problem. I guess, I was too lazy to think so I didn't try to solve this one in contest.
I missed one point while reading the problem, and I paid for that mistake in time :'(.

No triplet of scores contains scores that are more than 2 apart. - This one made my day like hell.

what are the possible sets.
Logic-1: If X is maximum then possible minimum will be X-2 in the triplet. Because possible triplets like this could be (X,X-2,X-2) or (X,X,X-2) or (X,X-1,X-2). Ofcourse they are surprising.
Logic-2: If X is maximum then possible minimum could be X-1 in the triplet.(Since Minimum X-1 is already ruled out in Logic-1). The possible triplets like this could be (X,X-1,X-1) or (X,X,X-1) - But these are not surprising Triplets
Logic-3: If X is maximum/minimum then possible triplet is (X,X,X) hehe Silly it not a Surprising Triplet.

So,
If a triplet is surprising then Maximum will be Average+ (1 or 2).
If a triplet is not surprising then Maximum will be Average+ (0 or 1).

If both are equal or more than P and maximum of surprising is equal or more than maximum of not surprising , then throw a count for it.
Simple it can be either surprising or not ....whats the big deal it has maximum than P in either case.
Save the urge to getting surprised for later, when you are sure that you will be more surprised with that triple.

import java.util.Scanner;

public class Problem2 {
 
 private static int isMaxSurprising(int sum){
  if(sum%3==0 && sum>0){
   return (sum/3)+1;
  }
  return (sum/3)+(sum%3);
 }
 
 private static int isNotMaxSurprising(int sum){
  if(sum%3==0 && sum>=0){
   return (sum/3);
  }
  return (sum/3)+1;
 }
 
 
 public static void main(String args[]) throws Exception{
  Scanner in= new Scanner(System.in);
  Scanner rIn= new Scanner(in.nextLine());
  
  int T=rIn.nextInt();
  
  for(int t=1;t<=T;t++){
   String nextLine=in.nextLine();
   rIn = new Scanner(nextLine);
   int N=rIn.nextInt();
   int S=rIn.nextInt();
   int p=rIn.nextInt();
   int count=0;
   for(int i=1;i<=N;i++){
    int sum=rIn.nextInt();
    int isMax=isMaxSurprising(sum);
    int isMaxNot=isNotMaxSurprising(sum);
    if(isMax >= isMaxNot && isMaxNot>=p){
     count++;
    }else if(S>0 && isMax >= isMaxNot && isMax >=p && isMaxNot <p){
     count++;
     S--;
    }
   }
   
   System.out.println("Case #"+t+": "+count);
  }
 }
}

Problem D. Hall of Mirrors
I'm still thinking about it.:P