SPOJ PSTRING (KMP + DP (Recursive)) Solution C++

Problem : www.spoj.com/problems/PSTRING

Algorithm : 

1. Compute KMPs DFA.
2. Apply DP.
  i) Either include a character or skip it.
 ii) Skip a character if it leads to a full substring match.

Code:

#include <iostream>
#include <cassert>
#include <string.h>

using namespace std;
const int mx = 10011 , my = 1024;
int f[my] , trans[my][26];
char X[mx] , Y[my], c ;
int dp[my][mx],xlen,ylen, inf = 1<<30;

#define mini(x, y) (x)<(y)?(x):(y)

int recurse(int matchedLength, int ind){
    if(ind==xlen)return 0;
    if(dp[matchedLength][ind]!=-1)return dp[matchedLength][ind];
    int ret1=inf, ret2=inf, ans=0; 

    int currentMatched = trans[matchedLength][X[ind]-'a'];
    if(currentMatched==ylen){
        ret2 = 1+recurse(currentMatched-1, ind+1);
    }else ret2 = recurse(currentMatched, ind+1);

    ret1 = 1+recurse(matchedLength, ind+1);
    if(ret1==0)ret1 = inf;

    ans = mini(ret1, ret2);
    dp[matchedLength][ind] = ans;
    return ans;
}

int main() {
 int k,i,j;
 while (gets(X)) {
  gets(Y);
  xlen = strlen(X) , ylen = strlen(Y);

  k=0;f[0]=0;

  for(i=1;i<ylen;++i){
      while(k>0 && Y[i]!=Y[k])k = f[k-1];
      if(Y[i] == Y[k])k++;
      f[i] = k;
  }

  for(i=0;i<my;++i)for(j=0;j<mx;++j)dp[i][j]=-1;

  for(i=0;i<ylen;++i){
      for(c='a';c<='z';++c){
          k = i;
          while(k>0 && Y[k] != c)k = f[k-1];
          if(Y[k] == c)k++;
          trans[i][c-'a'] = k;
       }
   }
   printf("%d\n", recurse(0, 0));
 }
}

Binary Tree Traversal using Recursive and Non-Recursive Methods [Java]

This program takes user input into a binary tree and the traverses the tress displaying the values using recursive and non recursive functions (Non recursive function for Inorder traversal):

Suppose the user inputs (-999 is taken as an end marker for input):

14 15 4 9 7 18 3 5 16 4 20 17 9 14 5 -999

The output of the program using both methods is (for Inorder traversal):

3 4 4 5 5 7 9 9 14 14 15 16 17 18 20 

Java Code:

import java.util.Scanner;

class nodetype{
    public int info;
    public nodetype left;
    public nodetype right;
}

public class NonRecursiveInorderTreeTraversal {
    
    //General tree construction code
    static nodetype getnode(){
        return new nodetype();
    }
    
    static nodetype maketree(int x){
        nodetype p = getnode();
        p.info = x;
        p.left = null;
        p.right = null;
        return p;
    }
    
    static void setleft(nodetype p, int x){
        if(p==null)
            System.out.println("void insertion\n");
        else if(p.left != null)
            System.out.println("invalid insertion\n");
        else p.left = maketree(x);
    }
    
    static void setright(nodetype p, int x){
        if(p==null)
            System.out.println("void insertion\n");
        else if(p.right != null)
            System.out.println("invalid insertion\n");
        else
         p.right = maketree(x);
    }
    
    /* Traversal in preorder, inorder and postorder */
    static void pretrav(nodetype tree){
        if(tree!=null){
            System.out.print(tree.info+" ");
            pretrav(tree.left);
            pretrav(tree.right);
        }
    }
    
    static void intrav(nodetype tree){
        if(tree!=null){
            intrav(tree.left);
            System.out.print(tree.info+" ");
            intrav(tree.right);
        }
    }
    
    static void posttrav(nodetype tree){
        if(tree!=null){
            posttrav(tree.left);
            posttrav(tree.right);
            System.out.print(tree.info+" ");
        }
    }
    /***   ***/

    
     private static int MAXSTACK = 100;
    

     //Code for the stack used
     static class stack{
         int top;
         nodetype[] item = new nodetype[MAXSTACK];
        
        {
            top = 0;
            item = new nodetype[MAXSTACK];
        }
        
         void push(nodetype it){
            if(top<MAXSTACK)
            item[top++] = it;
            else
                System.out.println("Stack Overflow!");
        }
         nodetype pop(){
            if(top!=0)
                return item[--top];
            else
                System.out.println("Nothing to pop!");
            return null;
        }
         boolean empty(){
            if(top==0){
                return true;
            }
            return false;
        }
    }
    

    //Non Recursive traversal method (inorder) using stack

    static void intrav2(nodetype tree){
        stack s = new stack();
        s.top = 0;
        
        nodetype p = tree;
        do{
            /* 
                travel down left branches as far as possible
                saving pointers to nodes passed
            */
            while(p!=null){
                s.push(p);
                p = p.left;
            } /*end while*/
            
            /*check if finished */
            if(!s.empty()){
                /* at this point the left subtree is empty */
                p = s.pop();
                System.out.print(p.info+" ");  /*visit the root*/
                p = p.right;                   /*traverse right subtree*/
            } /*end if*/
        }while(!s.empty() || p!= null);
    }/* end funtion */
    
    public static void main(String[] args){
        nodetype ptree;
        nodetype p = null, q;
        int number;
        
        System.out.println("Binary Tree Traversal\n\n");
        System.out.println("Enter numbers :");
        Scanner scan = new Scanner(System.in);
        number = scan.nextInt();
        
        ptree = maketree(number);
        
        while((number=scan.nextInt())!=-999){
            p = q = ptree;
            while(q!=null){
               p=q;
            if(number<p.info)
                q = p.left;
            else if(number>=p.info)
                q = p.right;
        }
    
         if (number<p.info)
            setleft(p, number);
         else if(number>=p.info)
            setright(p, number);
        }

        System.out.println("\nUsing recursive function intrav: ");        
        intrav(ptree);
        System.out.println("\nUsing non recursive function intrav2: ");
        intrav2(ptree);
    }
}