#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define FIRST 0
#define SECOND 1

char *genstring ( int s, int l )
{
   char *A;
   int i;

   A = (char *)malloc((l+1) * sizeof(char));
   A[l] = '\0';
   for (i=0; i<l; ++i) A[i] = 'a' + rand() % s;
   return A;
}

int issubseq ( char *S, int n, char *T, int m )
{
   int i, j;

   if (m > n) return 0;
   i = j = 0;
   while (i < n) {
      if (S[i] == T[j]) {
         if (++j == m) return 1;
      }
      ++i;
   }
   return 0;
}

char *stutter ( char *T, int m, int k )
{
   char *A;
   int i, j;

   A = (char *)malloc((m*k+1) * sizeof(char));
   A[m*k] = '\0';
   for (i=0; i<m; ++i) for (j=0; j<k; ++j) A[i*k+j] = T[i];
   return A;
}

void prnsubseq ( char *S, int n, char *T, int m )
{
   char *A;
   int i, j;

   printf("    %s\n", S);
   A = (char *)malloc((n+1)*sizeof(char));
   A[n] = '\0';
   for (i=0; i<n; ++i) A[i] = ' ';
   i = j = 0;
   while (i < n) {
      if (S[i] == T[j]) {
         A[i] = T[j];
         if (++j == m) break;
      }
      ++i;
   }
   printf("    %s\n", A);
   free(A);
}

int exhs ( char *S, int n, char *T, int m )
{
   int i, k;
   char *A;

   k = 0;
   for (i=1; i<=n/m; ++i) {
      A = stutter(T,m,i);
      if (issubseq(S,n,A,m*i)) {
         k = i;
         /* prnsubseq(S,n,A,m*i); */
         free(A);
      } else {
         break;
      }
   }
   return k;
}

char *gethalf ( char *S, int n, int s, int parity )
{
   unsigned int *cnt;
   char *H;
   int i, j, k;

   cnt = (unsigned int *)malloc(s * sizeof(unsigned int));
   for (j=0; j<s; ++j) cnt[j] = 0;

   H = (char *)malloc((s+(n+1)/2)*sizeof(char));
   for (i=k=0; i<n; ++i) {
      j = (int)(S[i] - 'a');
      if (cnt[j] == parity) H[k++] = S[i];
      cnt[j] ^= 1U;
   }
   H[k] = 0;
   free(cnt);
   return H;
}

int dnc1 ( char *S, int n, char *T, int m, int s )
{
   char *S1, *S2, *A;
   int k1, k2, k;

   if (n < 2*m) return issubseq(S,n,T,m);
   S1 = gethalf(S,n,s,FIRST);
   S2 = gethalf(S,n,s,SECOND);
   k1 = dnc1(S1,strlen(S1),T,m,s);
   k2 = dnc1(S2,strlen(S2),T,m,s);
   free(S1); free(S2);
   k = k1 + k2 + 1;
   A = stutter(T,m,k);
   if (issubseq(S,n,A,m*k)) {
      free(A);
   } else {
      --k;
      free(A);
      if (k == 0) return 0;
      A = stutter(T,m,k);
      if (issubseq(S,n,A,m*k)) {
         free(A);
      } else {
         --k;
         free(A);
         if (k == 0) return 0;
      }
   }
   /* printf("    k1 = %d, k2 = %d, k = %d\n", k1, k2, k); */
   return k;
}

int dnc2 ( char *S, int n, char *T, int m, int s )
{
   char *S1, *A;
   int k1, k;

   if (n < 2*m) return issubseq(S,n,T,m);
   S1 = gethalf(S,n,s,FIRST);
   k1 = dnc2(S1,strlen(S1),T,m,s);
   free(S1);
   k = 2 * k1 + 1;
   A = stutter(T,m,k);
   if (issubseq(S,n,A,m*k)) {
      free(A);
   } else {
      --k;
      free(A);
      if (k == 0) return 0;
      A = stutter(T,m,k);
      if (issubseq(S,n,A,m*k)) {
         free(A);
      } else {
         --k;
         free(A);
         if (k == 0) return 0;
      }
   }
   return k;
}

int main ( int argc, char *argv[] )
{
   int s, n, m, k;
   char *S, *T, *A;

   if (argc > 3) {
      s = atoi(argv[1]);
      n = atoi(argv[2]);
      m = atoi(argv[3]);
   } else {
      printf("Usage: ./a.out alphabet_size |S| |T|\n");
      scanf("%d%d%d", &s, &n, &m);
   }
   srand((unsigned int)time(NULL));

   printf("s = %d\nn = %d\nm = %d\n\n", s, n, m);
   S = genstring(s,n); printf("S = %s\n", S);
   T = genstring(s,m); printf("T = %s\n", T);

   printf("\n+++ Exhaustive search\n");
   k = exhs(S,n,T,m);
   printf("    k = %d\n", k);

   printf("\n+++ Divide and Conquer Strategy 1\n");
   k = dnc1(S,n,T,m,s);
   printf("    k = %d\n", k);

   printf("\n+++ Divide and Conquer Strategy 2\n");
   k = dnc2(S,n,T,m,s);
   printf("    k = %d\n", k);

   printf("\n+++ The subsequence is:\n");
   A = stutter(T,m,k);
   prnsubseq(S,n,A,m*k);

   free(S); free(T); free(A);

   exit(0);
}