算法1

破环为链+DP求最大公共子串+kruskal求最大生成树 $O(n^2)$

blablabla

时间复杂度

参考文献

java 代码

//艹，题目是环形字符串
import java.util.*;
import java.io.*;
import java.math.*;
public class Main {

  //完全图，最大生成树，kruskal，用完全图存还是直接边数组？
  static int N=205,n=0;
  static Edge[] e=new Edge[N*N-1];
  //
  static int[] p=new int[N];
  public static int find(int x){
    if(p[x]!=x)return p[x]=find(p[x]);
    else return p[x];
  }
  public static void union(int x,int y){
    p[find(y)]=find(x);
  }
  //
  public static void kruskal(){
    Arrays.sort(e,0,n*(n-1),(Edge a,Edge b)->{
        return b.z-a.z;
    });
    int cnt=0,res=0;
    for(int i=0;i<n*(n-1);i++){
      //每次若最大的边不构成连通集，将其加入，由于题意，这个生成树是一定存在的，没有孤立点
      int a=e[i].x,
          b=e[i].y,
          c=e[i].z;
      if(find(a)!=find(b)){
        cnt++;
        res+=c;
        union(a,b);
      }
      if(cnt==n-1)break;
    }
    System.out.println(res);
  }
  //并不是最长公共子序列
  static String[] str=new String[N];
  static int M=55,m=0;
  static int[][] f=new int[M*2][M*2];
  public static int bigComstr(String stra,String strb){
    int res=0;
    char[] a=stra.toCharArray(),
            b=strb.toCharArray();
    for(int i=1;i<=2*m;i++){
      for(int j=1;j<=2*m;j++){
        if(a[i-1]==b[j-1]){
          f[i][j]=f[i-1][j-1]+1;
          res=Math.max(res,f[i][j]);
        }
        else f[i][j]=0;
      }
    }
    res=Math.min(res,m);
    return res;
  }
    public static void main(String[] args) {
        for(int i=0;i<N;i++)p[i]=i;
        //
        Scanner scanner = new Scanner(System.in);
        n=scanner.nextInt();
        m=scanner.nextInt();
        scanner.nextLine();
        for(int i=0;i<n;i++){
          str[i]=scanner.nextLine();
          str[i]=str[i]+str[i];//破环为链
        }
        //get edges
        int cnt=0;
        for(int i=0;i<n;i++){
          for(int j=0;j<n;j++){
            if(i!=j){
                e[cnt++]=new Edge(i,j,bigComstr(str[i],str[j]));
            }
          }
        }
        kruskal();
        scanner.close();
    }
}
class Edge{
  public int x;
  public int y;
  public int z;
  Edge(int x,int y,int z){
    this.x=x;
    this.y=y;
    this.z=z;
  }
}