给定一个 query 和一个 text,均由小写字母组成。要

int GetLCSLength(int m, int n, char *str1, char *str2) {
 int max = 0;
 int *array = (int *)malloc(m * n * sizeof(int));
 memset(array, 0, sizeof(array));
 for (int i = 0; i < m; i++) {
 for (int j = 0; j < n; j++) {
 if (str1[i] == str2[j]) {
 if (i > 0 && j > 0) {
 array[i][j] = array[i - 1][j - 1] + 1;
 } else {
 array[i][j] = 1;
 }
 if (array[i][j] > max) {
 max = array[i][j];
 }
 }
 }
 }

 return max;
}

public class QueryText {
 public int maxLengthInQuery(char[] query,char[] text){
 int[] length = new int[text.length];
 for(int i = 0;i<text.length;i++){
 int size = 0;
 int temp = i;
 for(int j = query.length - 1 ;j >= 0 ;){
 if(text[i] == query[j])
 {
 size ++;
 i--;
 j--;
 if(i<0){
 break;
 }
 }
 else 
 {
 if( j == query.length - 1){
 while(query[j] != text[i])
 j--;
 }else{
 break;
 }
 }
 }
 length[temp] = size;
 i = temp;
 }
 return Max(length);
 }

 public int Max(int[] arr){
 int max = arr[0];
 for(int i = 1;i<arr.length;i++){
 if(arr[i] > max)
 max = arr[i];
 }
 return max;
 }
 
 public static void main(String[] args) {
 char[] query = {'a','c','b','a','c'};
 char[] text = {'a','c','a','c','c','b','a','b','b'};
 QueryText q = new QueryText();
 System.out.println(q.maxLengthInQuery(query, text));
 }
}

	

最长公共子序列

http://www.cnblogs.com/ErinCodeMM/archive/2012/10/30/2747042.html

http://www.cnblogs.com/zhangchaoyang/articles/2012070.html

#include <iostream>
#include <string>
#include<stdio.h> 
using namespace std;
void main()
{
	string query="acbac";
	string text="acaccbabb";
	char *p=0;
	char q[20],t[20];
	int flag=0;
	int len=query.size();
	for (int i=len;i>=1;i--)
	{
		for (int j=0;j<=len+1-i;j++)  //此处要修改
		{
			strcpy(q,query.c_str());
			strcpy(t,text.c_str());
			p=strstr(t,q);
			if(p)
			{
				flag=1;
				break;
			}
			else
			{
				query.replace(0,len,query,j,i-1);//此处要修改
			}
		}
		if(flag==1)
		{
			cout<<"最大子串长度为："<<strlen(q)<<endl;
			break;
		}
		
	}

}

//void get_next(SString T);
void KmpString::get_next(SString T) //获取next列表
{
	std::cout << T.getCh() << std::endl;
	//这来两个数j代表着是模式串中的位置，i用来计数在模式串中的遍历位置，防止访问越界
	//首先我们初始化我们的next的第一个数和我们的起始比较的位置
	//初始化我们的next
	this->next = new int[20]{0};
	//我们首先设定一个参数遍历主串，然后设定一个参数遍历子串
	int j = 1, i = 0;	//子串的那个还没开始比较是为0
	this->next[1] = 0;	//第一个，设定为0表示主节点是第一个的时候也就是j = 1的时候，没哟从复的地方
	unsigned char *t = T.getCh();		//得到我们的字符串
	if (T.getLength() > 1)		//首先我们传进来要进行求比较位置的参数不能为空，也就是长度大于0
	{
		//循环遍历主串
		while (j < T.getLength())
		{
			//判断子串的位置是否是0从新开始，或者我们主串的位置和子串的位置比较
			if (i == 0 || t[j] == t[i])
			{
				//如果是第一个或者匹配相等
				++j;	//主串
				++i;	//子串
				this->next[j] = i;  //我们把主串的和子串匹配的位置记住
			}
			else
			{
				//如果这个p:***:k不相等，也就是t[j] ！= t[i]不相等的时候
				i = next[i];
			}
		}
	}

}

/*
利用模式T的next的值，求T在S主串中第pos个字符之后的位置
*/
int KmpString::index_KMP(SString T, unsigned int pos)
{
	int i = pos, j = 1;  //第一个是我们主串开始的位置，后面是我们模式串开始的位置
	unsigned char *s = this->getCh();
	unsigned char *t = T.getCh();
	while (i <= this->getLength() && j <= T.getLength())
	{
		//在长度范围内
		if (j == 0 || s[i] == t[j])
		{
			++i;
			++j;
		}
		else
		{
			j = next[j];
		}
	}
	//循环结束之后我们判断一下是遍历到了最后的没有找到，还是找到了
	if (j > T.getLength()) //说明匹配到了最后的位置
		return i - T.getLength();
	else
		return 0;
}

package test;

/**
 * Created by asus on 2015/8/27.
 */

import java.util.Scanner;

public class LongestKMP {

    static int[] fail;

    /**
     * 初始化我们的失败数组，用来记忆比如acbac，此时的fail是-1、0、0、0、1你在比较第二个a的时后失败了那么就会到0 在失败就-1
     *
     * @param word
     */
    static void init(String word) {
        fail = new int[word.length()];
        fail[0] = -1;
        for (int i = 0, j = -1, len = word.length(); i < len - 1; ++i, ++j) {
            while (j != -1 && word.charAt(j) != word.charAt(i)) {
                j = fail[j];
            }
            fail[i + 1] = j + 1;
        }
    }

    static int solve(String pattern, String text) {
        init(pattern);
        int res = 0;
        for (int i = 0, j = 0, len = text.length(); i < len; ++i, ++j) {
            while (j != -1 && pattern.charAt(j) != text.charAt(i)) {
                j = fail[j];
            }
            if (j == pattern.length() - 1) {
                res++;
                j = fail[j];
                while (j != -1 && pattern.charAt(j) != text.charAt(i)) {
                    j = fail[j];
                }
            }
        }
        return res;
    }


    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        String pattern = in.nextLine();
        String text = in.nextLine();
        k:
        for (int i = pattern.length(); i > 0; i--) {
            for (int j = 0; j < pattern.length() - i + 1; j++) {
                String temp = pattern.substring(j, i + j);
                if (solve(temp, text) >= 1) {
                    System.out.print(i);
                    break k;
                }
            }
        }

        in.close();
    }
}

}

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

/**
 * @program: test-lrg
 * @description: 编程题2
 * @author: Arell
 * @create: 2019-12-21 10:55
 **/
public class AliTest02 {
    public static void main(String[] args) {
        /*
        *
    给定一个 query 和一个 text,均由小写字母组成。要求在 text 中找出以同样的顺序连 续出现在 query 中的最长连续字母序列的长度。
    例如, query 为“acbac”,text 为 “acaccbabb”,那么 text 中的“cba”为最长的连续出现在 query 中的字母序列,因此, 返回结果应该为其长度 3
    */
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入query字符串:");
        String query = scanner.next();
        System.out.println("请输入text字符串:");
        String text = scanner.next();
        AliTest02 aliTest02 = new AliTest02();
        int length = aliTest02.getLength(query, text);
        System.out.println(length);


    }

    private int getLength(String query, String text) {
        //先转换为数组
        String[] queryArr = query.split("");
        String[] textArr = text.split("");
        ArrayList<Integer> countList = new ArrayList<>();
        for (int i = 0; i < queryArr.length; i++) {
            //循环,以开头的字母为标识,添加计数器
            String q = queryArr[i];
            int count = 0;
            for (int j = 0; j < textArr.length; j++) {
                compare(countList, count, i, j, queryArr, textArr);
            }
        }
        Collections.sort(countList);

        return countList.get(countList.size() - 1);
    }

    private void compare(List<Integer> countList, int count, int m, int n, String[] query, String[] text) {
        if (query[m].equals(text[n])) {
            //如果相等,计数+1,索引都往后推1
            count++;
            m++;
            n++;
            if (m <= query.length - 1) {
                if (n <= text.length - 1) {
                    //递归调用
                    compare(countList, count, m, n, query, text);
                }else {
                    countList.add(count);
                }
            }else {
                countList.add(count);
            }
        } else {
            countList.add(count);
        }
    }

}

import java.util.*;  public class Main{ //比较两个字符串的最大公共子串   public static int findMax(String query, String text)//在text中找出以相同的顺序连续出现在query中  { int len1=query.length(); //计算query的长度  int len2=text.length(); //计算text的长度  //int [][]data=new int[len1][len2];   if(query==null||text==null)
        { return 0;  } if(len1==0||len2==0)
        { return 0;  } int sum=0;  int [][]array=new int[len1][len2];  for(int i=0;i<len1;i++)
        { for(int j=0;j<len2;j++)
            { if(query.charAt(i)==text.charAt(j))
                { if((i==0)||(j==0))
                    {
                        array[i][j]=1;  } else  {
                        array[i][j]=array[i-1][j-1]+1;  } if(array[i][j]>sum)
                    {
                        sum=array[i][j];   }
                }
            }
        } return sum;   } public static void main(String []args)
    {
        Scanner scan=new Scanner(System.in);  while(scan.hasNext())
        {
            String query=scan.next();  String text=scan.next();   int len=findMax(query,text);   System.out.println(len);  }
    }
}

import java.util.Scanner; public class MaxString { public int MaxStr(String query, String text) {  for (int i = 0; i < query.length(); i++) 
          { for (int j = 0; j < i + 1; j++) {
                String substring = query.substring(j, query.length() - i + j);  if (text.contains(substring))  return substring.length();
            }
        } return 0;
    }  public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        MaxString maxstr = new MaxString();  while (scanner.hasNext()) {
            String query = scanner.next();
            String text = scanner.next();
            System.out.println(maxstr.MaxStr(query, text));
        }
    }
}

import java.util.Scanner;
public class Main{

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
        while(sc.hasNext())
        {
        	String text,query;
        	query = sc.next();
        	text = sc.next();
        	int i= 0,j = 0,max = 0,tmpLen = 0; 
        	int len = 0;
        	while(len<query.length())
        	{
        		while(j<text.length() && i<query.length())
        		{
        			if(query.charAt(i)==text.charAt(j))
        			{
        				j++;
        				i++;
        				tmpLen++;
        			}
        			else
        			{
        				if(tmpLen == 0)
        				{
        					j++;
        				}
        				else
        				{
        					if(tmpLen>max)
        					{
        						max = tmpLen;
        					}
        					i = len;
    						tmpLen = 0;
        				}
        			}
        		}
        		i++;
        		j = 0;
        		len = i;
        		if(tmpLen>max)
            	{
        		   max = tmpLen;
            	}
        	}
        	System.out.println(max);
        }
	}

}

#include <iostream>
#include <string>

using namespace std;

bool KMP(string s, string t)
{
    int len1 = s.size();
    int len2 = t.size();
    int next[len1];
    int i = 0;
    int j = -1;
    next[0] = -1;
    while (i < len1-1)
    {
        if (j == -1 || s[i] == s[j])
        {
            i++;
            j++;
            next[i] = j;
         }
         else
            j = next[j];
     }
     int m = 0, n = 0;
     while (m < len1 && n < len2)
     {
        if (m == -1 || s[m] == t[n])
        {
            m++;
            n++;
         }
         else m = next[m];
     }
     if (m >= len1)
        return true;
     else
        return false;
}

int maxfit(string query, strng text)
{
   int len1 = query.size();
   int res = 0;
   for (int i = 0; i < len1; i++)
   {
       for (int j  = 0; j < len1; j++)
       {
           string str = query.substr(i, j-i+1);
           if (KMP(str, text))
               res = max(res, j-1+1);
        }
    }
    return res;
}

/*
 * 由于下一行的结果需要用到上一行的结果，所以在此使用了两个数组来保存结果
 * 如果我们是从后向前生成匹配结果，就只需要一个数组即可
 */
public class LCS_Test
{
	public int LCS(String s1,String s2)
	{
		int len = 0;
		char[] f1 = s1.toCharArray();
		char[] f2 = s2.toCharArray();
		int[] curr = new int[f2.length]; // 当前行的匹配结果
		int[] prev = new int[f2.length]; // 上一行的匹配结果
		for(int i = 0; i < f1.length; i++)
		{
			clear(curr);
			for(int j = 0; j < f2.length; j++)
			{
				if(f1[i] == f2[j])  // 如果匹配
				{
					if(j - 1 >= 0)  // 如果上一行当前列的前一个元素存在，则当前行的匹配结果为上一个当前列的前一个元素结果加一
					{
						curr[j] = prev[j - 1] +1;
						
					}
					else
						curr[j] = 1; // 否则，直接置为1
					if(curr[j] > len)
					{
						len = curr[j]; // len是用来保存最大长度的标志
					}
						
				}
				else
					curr[j] = 0;// 如果不匹配，则直接置为0
				
			}
			copy(prev, curr); // 在下一行匹配时，curr将变为prev
		}
		return len;
	}
	public void clear(int[] arr)
	{
		for(int i = 0; i < arr.length; i++)
			arr[i] = 0;
	}
	public void copy(int[] arr1, int[] arr2)
	{
		for(int i = 0; i < arr1.length; i++)
			arr1[i] = arr2[i];
	}
	public static void main(String [] args)
	{
		String s1 = "21232523311324";
		String s2 = "312123223445";
		LCS_Test ls = new LCS_Test();
		int length =ls.LCS(s1,s2);
		System.out.println(length);
	}
}

#include<iostream>
#include<string>
using namespace std;

int main(void)
{
	string query;
	string text;
	cout << "请输入query字符串：";
	cin >> query;
	cout << "请输入text字符串：";
	cin >> text;
	int m = query.size();
	int n = text.size();
	int arr[100][100] = {0};
	for (int i = 0; i < n;i++)
	{
		if (text[i]==query[0])
		{
			arr[0][i] = 1;
		}
	}
	for (int j = 0; j < m;j++)
	{
		if (text[0]==query[j])
		{
			arr[j][0] = 1;
		}
	}
	for (int i = 1; i < m;i++)
	{
		for (int j = 1; j < n;j++)
		{
			if (text[j]==query[i])
			{
				arr[i][j] = arr[i - 1][j - 1] + 1;
			}
		}
	}
	int max = 0;
	int hangbiao = 0;

	for (int i = 0; i < m;i++)
	{
		for (int j = 0; j < n;j++)
		{
			if (arr[i][j]>max)
			{
				max = arr[i][j];
				hangbiao = i-max+1;
			}
		}
	}
	cout << "最大子串长度：" << max << endl << "子串如下：" << endl;
	for (int i = 0; i < max;i++)
	{
		cout << query[hangbiao + i];
	}
	cout << endl;
	system("pause");
	return 0;
}