{ }codelper
字符串长度反转字符串P0143

标出两行的不同之处

第一行给出 a,第二行给出 b。
我们想对齐字符的列,显示两行在哪里不同。
首先,从开头起逐个字符对比 a 和 b,相同字符连续出现的最长长度记为 p。
然后,把 a 和 b 都去掉前面 p 个字符,从末尾起逐个字符对比剩下的两个字符串,相同字符连续出现的最长长度记为 s。
因此 p + s 不会超过两行中较短一行的长度。
输出的第一行是 p 和 s,用一个空格分隔。
如果 a 和 b 完全相同,到此结束(这时 s 为 0)。
否则再接着输出三行。
第二行是 "- " 后面接 a,第三行是 "+ " 后面接 b。
第四行是 (2 + p) 个空格后面接 w 个 ^。
w 是 a 改动部分的长度(a 的长度 − p − s)和 b 改动部分的长度(b 的长度 − p − s)中较大的那个。

输入
每行长度 1 到 1000,只用 ASCII 字符(编码 32~126)。
行首和行尾都不是空格
输出
一行(相同时)或四行
样例 1 · stdin
the quick brown fox
the quack brown fox
stdout
6 12
- the quick brown fox
+ the quack brown fox
        ^
样例 2 · stdin
aa
aaa
stdout
2 0
- aa
+ aaa
    ^
main.py
输入(stdin)

运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。

$ 就绪

请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。

其他语言怎么写?查看各语言题解 · 8 种语言题解

陷阱有三个。
第一,如果在整个字符串上数末尾相同的部分,会和开头相同的部分重叠。"aa" 和 "aaa" 从开头有 2 个字符相同,从整个字符串末尾也有 2 个相同,改动部分的长度就成了 −2。
必须去掉前面 p 个字符后,在剩下的部分上数。
第二,只按一行决定 ^ 的宽度,像 "print(x)" → "print(x, y)" 这样只插入的情况就一个 ^ 也没有。
第三,两行相同时只输出第一行。
反转用 Python t[::-1],Java new StringBuilder(t).reverse(),C# 用 Array.Reverse 反转字符数组再 new string(c),C++ std::string(t.rbegin(), t.rend()),Craykon t.反转()。
JS·TS 的字符串没有 reverse,要借助数组:[...t].reverse().join("")。
C 自然的做法是不反转,用 a[la - 1 - s] 从末尾数。
长度用 Python len(t),JS·TS t.length,Craykon t.长度,Java t.length(),C# t.Length,C strlen(t),C++ t.size()。
C++ 的 size() 是无符号数,如果 a.size() - p - s 变成负数,就会绕成一个极大的数;不重叠地数就不会出现负数。
比较字符串是否相同时,只有 Java 要用 equals(== 问的是是不是同一个对象)。

Pythonmain.py · 18 行
def common_prefix(x, y):    k = 0    while k < len(x) and k < len(y) and x[k] == y[k]:        k += 1    return k  a = input()b = input()p = common_prefix(a, b)# 앞에서 같은 부분을 뺀 나머지를 뒤집으면, 뒤에서 같은 부분이 앞에서 같은 부분이 된다s = common_prefix(a[p:][::-1], b[p:][::-1])print(p, s)if a != b:    print("- " + a)    print("+ " + b)    width = max(len(a) - p - s, len(b) - p - s)    print("  " + " " * p + "^" * width)
JavaScriptmain.js · 19 行
const [a, b] = require("fs").readFileSync(0, "utf8").split("\n"); function commonPrefix(x, y) {  let k = 0;  while (k < x.length && k < y.length && x[k] === y[k]) k++;  return k;}// 문자열에는 reverse가 없어서 배열로 바꿔 뒤집고 다시 잇는다const reverse = (t) => [...t].reverse().join(""); const p = commonPrefix(a, b);const s = commonPrefix(reverse(a.slice(p)), reverse(b.slice(p)));const out = [`${p} ${s}`];if (a !== b) {  out.push("- " + a, "+ " + b);  const width = Math.max(a.length - p - s, b.length - p - s);  out.push("  " + " ".repeat(p) + "^".repeat(width));}console.log(out.join("\n"));
TypeScriptmain.ts · 20 行
import { readFileSync } from "node:fs";const [a, b]: string[] = readFileSync(0, "utf8").split("\n"); function commonPrefix(x: string, y: string): number {  let k = 0;  while (k < x.length && k < y.length && x[k] === y[k]) k++;  return k;}// 문자열에는 reverse가 없어서 배열로 바꿔 뒤집고 다시 잇는다const reverse = (t: string): string => [...t].reverse().join(""); const p: number = commonPrefix(a, b);const s: number = commonPrefix(reverse(a.slice(p)), reverse(b.slice(p)));const out: string[] = [`${p} ${s}`];if (a !== b) {  out.push("- " + a, "+ " + b);  const width: number = Math.max(a.length - p - s, b.length - p - s);  out.push("  " + " ".repeat(p) + "^".repeat(width));}console.log(out.join("\n"));
JavaMain.java · 31 行
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader; public class Main {    static int commonPrefix(String x, String y) {        int k = 0;        while (k < x.length() && k < y.length() && x.charAt(k) == y.charAt(k)) k++;        return k;    }     static String reverse(String t) {        return new StringBuilder(t).reverse().toString();    }     public static void main(String[] args) throws IOException {        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));        String a = in.readLine(), b = in.readLine();        int p = commonPrefix(a, b);        int s = commonPrefix(reverse(a.substring(p)), reverse(b.substring(p)));        StringBuilder out = new StringBuilder();        out.append(p).append(' ').append(s).append('\n');        if (!a.equals(b)) { // == 는 같은 객체인지를 묻는다            out.append("- ").append(a).append('\n');            out.append("+ ").append(b).append('\n');            int width = Math.max(a.length() - p - s, b.length() - p - s);            out.append("  ").append(" ".repeat(p)).append("^".repeat(width)).append('\n');        }        System.out.print(out);    }}
C#Main.cs · 33 行
using System; class Program{    static int CommonPrefix(string x, string y)    {        int k = 0;        while (k < x.Length && k < y.Length && x[k] == y[k]) k++;        return k;    }     static string Reverse(string t)    {        char[] c = t.ToCharArray();        Array.Reverse(c);        return new string(c);    }     static void Main()    {        string a = Console.ReadLine(), b = Console.ReadLine();        int p = CommonPrefix(a, b);        int s = CommonPrefix(Reverse(a.Substring(p)), Reverse(b.Substring(p)));        Console.WriteLine($"{p} {s}");        if (a != b)        {            Console.WriteLine("- " + a);            Console.WriteLine("+ " + b);            int width = Math.Max(a.Length - p - s, b.Length - p - s);            Console.WriteLine("  " + new string(' ', p) + new string('^', width));        }    }}
C++main.cpp · 25 行
#include <algorithm>#include <iostream>#include <string> size_t commonPrefix(const std::string& x, const std::string& y) {    size_t k = 0;    while (k < x.size() && k < y.size() && x[k] == y[k]) k++;    return k;} int main() {    std::string a, b;    std::getline(std::cin, a);    std::getline(std::cin, b);    size_t p = commonPrefix(a, b);    // 앞에서 같은 p글자를 뺀 나머지를 거꾸로(rbegin~rend) 만든다    std::string ra(a.rbegin(), a.rend() - p), rb(b.rbegin(), b.rend() - p);    size_t s = commonPrefix(ra, rb);    std::cout << p << ' ' << s << '\n';    if (a != b) {        std::cout << "- " << a << "\n+ " << b << '\n';        size_t width = std::max(a.size() - p - s, b.size() - p - s);        std::cout << "  " << std::string(p, ' ') << std::string(width, '^') << '\n';    }}
Cmain.c · 25 行
#include <stdio.h>#include <string.h> int main(void) {    static char a[1100], b[1100];    if (!fgets(a, sizeof a, stdin) || !fgets(b, sizeof b, stdin)) return 0;    a[strcspn(a, "\n")] = '\0';    b[strcspn(b, "\n")] = '\0';    int la = (int)strlen(a), lb = (int)strlen(b);    int p = 0;    while (p < la && p < lb && a[p] == b[p]) p++;    /* 뒤집지 않고 끝에서부터 센다. 앞에서 같은 p글자는 다시 세지 않는다 */    int s = 0;    while (s < la - p && s < lb - p && a[la - 1 - s] == b[lb - 1 - s]) s++;    printf("%d %d\n", p, s);    if (strcmp(a, b) != 0) {        printf("- %s\n+ %s\n", a, b);        int ma = la - p - s, mb = lb - p - s;        int width = ma > mb ? ma : mb;        printf("  %*s", p, "");        for (int k = 0; k < width; k++) putchar('^');        putchar('\n');    }    return 0;}
Craykonmain.cray · 23 行
a = 控制台.读行();b = 控制台.读行();p = commonPrefix(a, b);// 앞에서 같은 부분을 뺀 나머지를 뒤집으면, 뒤에서 같은 부분이 앞에서 같은 부분이 된다s = commonPrefix(a.截取(p).反转(), b.截取(p).反转());控制台.输出(p + " " + s);如果 (a != b){    控制台.输出("- " + a);    控制台.输出("+ " + b);    width = 数学.较大值(a.长度 - p - s, b.长度 - p - s);    控制台.输出("  " + " ".重复(p) + "^".重复(width));} commonPrefix(x, y){    k = 0;    当 (k < x.长度 && k < y.长度 && x[k] == y[k])    {        k += 1;    }    返回 k;}