C - Common Subsequence

Description

A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = <x1, x2, ..., xm> another sequence Z = <z1, z2, ..., zk> is a subsequence of X if there exists a strictly increasing sequence <i1, i2, ..., ik> of indices of X such that for all j = 1,2,...,k, xij = zj. For example, Z = <a, b, f, c> is a subsequence of X = <a, b, c, f, b, c> with index sequence <1, 2, 4, 6>. Given two sequences X and Y the problem is to find the length of the maximum-length common subsequence of X and Y.
The program input is from a text file. Each data set in the file contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct. For each set of data the program prints on the standard output the length of the maximum-length common subsequence from the beginning of a separate line.

 

Input

On the first line of the input, there is a single positive integer n, telling the number of test scenarios to follow. Each test scenario begins with a line containing a single positive integer p<40000, the number of ports on the two functional blocks. Then follow p lines, describing the signal mapping: On the i:th line is the port number of the block on the right side which should be connected to the i:th port of the block on the left side.

 

Output

For each test scenario, output one line containing the maximum number of signals which may be routed on the silicon surface without crossing each other.

 

Sample Input

    
     

      
      abcfbc abfcab
programming contest 
abcd mnp 
    
     

 

Sample Output

    
     

      
      4
2
0 
    
     

   Find the maximum common subsequence of two strings

str1[I]、str2b[I] Represents two strings respectively

maxlen[I][j] Before the first string I Before the first and second strings j Maximum common subsequence of characters

When str[I-1]=str[j-1] when maxlen[I][j]=maxlen[I-1][j-1]+1

When unequal maxlen[I][j]=max(maxlen[I-1][j],maxlen[I][j-1]}

The code is as follows

#include<stdio.h>
#include<string.h>
int Max(int a,int b)
{
	if(a>b) b=a;
	return b;
}
int maxlen[10001][10001];
int main()
{
	char str1[100001];
	char str2[100001];
	int i,j;
	while(scanf("%s %s",str1,str2)!=EOF)
	{
		int len1,len2;
		len1=strlen(str1);
		len2=strlen(str2);
		for(i=0;i<=len1;i++)
		{
			maxlen[i][0]=0;
		}
		for(j=0;j<=len2;j++)
		{
			maxlen[0][j]=0;
		}
    	for(i=1;i<=len1;i++)
    	{
	    	for(j=1;j<=len2;j++)
	    	{
	    		if(str1[i-1]==str2[j-1])
	    		{
	    			maxlen[i][j]=maxlen[i-1][j-1]+1;
	    			
	    		}
	    		else 
	    		{
	    			maxlen[i][j]=Max(maxlen[i-1][j],maxlen[i][j-1]);
	    		}
	    	}
    	}
    	printf("%d\n",maxlen[len1][len2]);
    }
}