小猿有两张分别写着字符串s1、s2的纸条，字符串由大小写字母组成。小猿会进行n次操作，每次操作时小猿会选择其中一张纸条，把它从左侧撕下一段或把它全部交给你。你按收到纸条的顺序，从左到右将收到的n张纸条拼接成一张新的纸条。 已知字符串s1、s2，求是否存在一种方案使新纸条上的字符串与s3相同、且满足n<=K。-笔试面试资料

小猿有两张分别写着字符串s1、s2的纸条，字符串由大小写字母组成。小猿会进行n次操作，每次操作时小猿会选择其中一张纸条，把它从左侧撕下一段或把它全部交给你。你按收到纸条的顺序，从左到右将收到的n张纸条拼接成一张新的纸条。

已知字符串s1、s2，求是否存在一种方案使新纸条上的字符串与s3相同、且满足n<=K。

笔寞

import java.util.*; public class Main {     static int T;     static boolean getAns(String a, String b, String c, int maxn) {         char[] sa = a.toCharArray();         char[] sb = b.toCharArray();         char[] sc = c.toCharArray();         int l1 = sa.length;         int l2 = sb.length;         int l3 = sc.length;          int[][][] f = new int[l1 + 1][l3 + 1][3];         for (int i = 0; i <= l1; i++)             for (int j = 0; j <= l3; j++)                 for (int k = 0; k <= 1; k++)                     f[i][j][k] = 10000;         int num;         int rmax;         rmax = Math.min(l3, l2);          for (int j = 1; j <= Math.min(l2, l3); j++)             if (sb[j - 1] == sc[j - 1]) {                 f[0][j][1] = 1;                 if (j == l3 && maxn >= 1)                     return true;             } else {                 break;             }          for (int i = 1; i <= l1; i++) {             rmax = Math.min(l3, i + l2);             for (int j = i; j <= rmax; j++) {                 num = f[i][j][0];                 if (sa[i - 1] == sc[j - 1]) {                     if(i == 1 && j == 1)                         num = f[1][1][0] = 1;                     num = Math.min(num, f[i - 1][j - 1][0]);                     num = Math.min(num, f[i - 1][j - 1][1] + 1);                     f[i][j][0] = num;                     if (j == l3 && num <= maxn)                         return true;                 }                 if (j > i) {                     num = f[i][j][1];                     if (sb[j - i - 1] == sc[j - 1]) {                         num = Math.min(num, f[i][j - 1][0] + 1);                         num = Math.min(num, f[i][j - 1][1]);                        // f[i][j][1] = Math.min(f[i][j][1], Math.min(f[i][j - 1][0], f[i][j - 1][1]));                         f[i][j][1] = num;                         if (j == l3 && num <= maxn)                             return true;                     }                 }             }         }         return false;     }     public static void main(String[] args) {         Scanner reader = new Scanner(System.in);         T = reader.nextInt();         reader.nextLine();         String[] strs;         int num;         for (int i = 1; i <= T; i++) {             strs = reader.nextLine().split("\s+");             num = Integer.parseInt(strs[3]);             if (getAns(strs[0], strs[1], strs[2], num))                 System.out.println("1");             else                 System.out.println("0");         }     } } 

今天 11:04:07 回复(0)