Slash the string-tester

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

void computeLPSArray(char *pat, int M, int *lps);

int KMPSearch(char *pat, char *txt)
{
    int M = strlen(pat);
    int N = strlen(txt);
    int *lps = (int *)malloc(sizeof(int)*M);
    int j  = 0;
    computeLPSArray(pat, M, lps);
    int ma=0;
    int i = 0;
    while (i < N)
    {
      if (pat[j] == txt[i])
      {
        j++;
        i++;
      }
      if (j > ma)
      {
        //printf("Found pattern at index %d \n", i-j);
        ma=j;
        //j = lps[j-1];
      }

      else if (i < N && pat[j] != txt[i])
      {
        if (j != 0)
         j = lps[j-1];
        else
         i = i+1;
      }
    }
    free(lps);
    return ma;
}

void computeLPSArray(char *pat, int M, int *lps)
{
    int len = 0;
    int i;

    lps[0] = 0;
    i = 1;
    while (i < M)
    {
       if (pat[i] == pat[len])
       {
         len++;
         lps[i] = len;
         i++;
       }
       else
       {
         if (len != 0)
         {
           len = lps[len-1];
         }
         else
         {
           lps[i] = 0;
           i++;
         }
       }
    }
}
int dp[2005];
int dp2[2005];
char p[2005];
char ch[2005];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int j,ans=0,i;
        string s;
        cin>>s;
        int curi=0,curj=s.length(),tot=0;
        while(curi<curj)
        {
            //printf("%d %d\n",curi,curj);
            memset(dp,0,sizeof(dp));
            int pos=-1;
            for(i=curi;i<curj;i++)
            {
                int len=0;
                for(j=i+1;j<curj;j++)
                {
                    p[len]=s[j-1];
                    ch[len++]=s[j];
                }
                p[len]=s[j-1];
                ch[len]='\0';
                len++;
                p[len]='\0';
                int val=KMPSearch(p,ch);
                if(val==0)
                    break;
                pos=i;
                dp[i]=val;
            }
            for(i=0;i<2001;i++)
                dp2[i]=10000;
            if(pos>0)
            {
                dp2[curi]=0;
                for(i=curi;i<pos+1;i++)
                {
                    for(j=1;j<=dp[i];j++)
                        dp2[j+i]=min(dp2[j+i],dp2[i]+1);
                }
                curi=pos+1;
                ans=ans+dp2[pos+1];
            }
            int pr=0;
            for(j=curi;j<curj-1;j++)
                ch[pr++]=s[j];
            ch[pr]='\0';
            int fl=0;
            int yy=0;
            //printf("curi-> %d\n",curi);
            for(i=curj-1;i>=0;i--)
            {
                int len=0;
                for(j=i;j<curj;j++)
                {
                    p[len++]=s[j];
                }
                p[len]='\0';
                //printf("%s %s\n",p,ch);
                int val=KMPSearch(p,ch);
                //printf("%d\n",val);
                if(val==len){
                    fl=1;
                    yy=i;
                }
                else
                    break;
            }
            if(fl)
            {
                curj=yy;
            }
            else
                curi++;
            //printf("%d %d\n",curi,curj);
            ans++;
            //tot=1;
        }
        printf("%d\n",ans);
    }
    return 0;
}