问题标题: 酷町堂：1470 循环公共字符串30豆子

Question

0

已解决

周琪岳

资深光能

#include <iostream>
#include <cstring>
#include <string>

using namespace std;

string s1, a, b;
int ans, f[1005][1005];

int main() {
	getline(cin, s1);
	getline(cin, b);
	for(int i=0; i<s1.size(); i++) {
		memset(f, 0, sizeof(f));
		a = s1.substr(i, s1.size() - i) + s1.substr(0, i);
		int n = a.length(), m = b.length();
		string a1 = " " + a;
		string b1 = " " + b;
		for(int j=1; j<=n; j++) {
			for(int k=1; k<=m; k++) {
				if(a1[j] == b1[k]) {
					f[j][k] = f[j-1][k-1] + 1;
				} else{
					f[j][k] = max(f[j][k-1], f[j-1][k]);
				}
			}

		}
		ans = max(ans, f[n][m]);
	}
	cout << ans;
	return 0;
}

在线求教，谢谢

周琪岳在2021-02-03 13:15:03追加了内容

@汪恺恒我的意思是用线性DP写，不是套函数

Answer 1

已采纳

周琪岳

初级守护

我自己AC了

Answer 2

汪恺恒

中级启示者

不用这么麻烦，一个字符串求子串的函数就搞定了

首先输入字符串

s1=a+a;//首尾相连
    s2=b+b;
    int len1=s1.size(),len2=s2.size();
    if(len1>len2){//寻找最短的字符串
        swap(s1,s2);
        len1=s1.size();
        len2=s2.size();
    }

之后进行查找

循环(int i=0;i<=len1/2;i++){
        循环(int j=1;j<=len1/2;j++){//枚举两个下标
            int x=s2.find(s1.substr(i,j));//在s2中查找，截取的字符串是否存在
            if(x!=-1){
                if(j>ans){
                    ans=j;//更新最大长度
                }
            }
        }
    }

最后输出ans就AC了

//我的问题

Answer 3

张天璨

新手天翼

easy

问题标题: 酷町堂：1470 循环公共字符串30豆子

3 个回答: