将 s1 转换为以 s2 为子串的回文

Question

https://discuss.codechef.com/t/given-string-s1-and-s2-how-to-convert-given-string-s1-with-minimum-changes-to-palindrome-which-includes-s2-as-substring/69769

有人能帮我理解这段代码吗

#include<bits/stdc++.h>

使用命名空间标准；

int main(){

string s1,s2;
cin>>s1>>s2;
int l1=s1.length(),l2=s2.length();
int ans=INT_MAX;
if(l2>l1){

    cout<<-1<<endl; // not possible
    return 0;
}
for(int i=0 ; i<l1-l2+1 ; i++){

    string temp=s1.substr(0,i)+s2+s1.substr(i+l2); // place s2 in all possible positions in s1
    int cost=0;
    // calculate cost to place s2
    for(int j=i ; j<i+l2 ; j++){

        if(s1[j]!=temp[j])
            cost++;
    }
    int z=0;
    // find the cost to convert new string to palindrome

谁能解释一下下面的代码

    for(int j=0 ; j<ceil(l1/2.0) ; j++){

        if((j<i || j>=i+l2) && temp[j]!=temp[l1-j-1]) //(explain please) if s2 is in the first half of new string
            cost++;
        else if(temp[j]!=temp[l1-j-1] && (l1-j-1<i || l1-j-1>=i+l2)) // (explain please)if s2 is in the second half of new string
            cost++;
        else if(temp[j]!=temp[l1-j-1]){ // if s2 is in both halves

            z=1;
            break;
        }
    }
    if(z==0)
        ans=min(ans,cost);
}
if(ans==INT_MAX)
    cout<<-1<<endl;
else
    cout<<ans<<endl;
return 0;

}

Answer 1

回文...向后与向前相同... 代码的第一部分将 s2 覆盖在 s1 中从某个位置开始的字符之上：i。字符串 temp 是 s1 的前 i 个字符，然后是 s2 的所有字符，然后是 s1 中未被掩盖的任何字符。 temp的长度应该是s1的长度。

在 j 循环中，您迭代 0 到 s1 大小的一半向上舍入。

您的第一个 'please explain' 是查看字符串 temp 中的索引 j 是否落在属于 s1 的字符上（无论是在 s2 字符之前还是之后）。它还会查看 temp 中索引 j 处的字符是否与它在反面的位置匹配（即该字符和它的镜像是否已经相等，因为它们必须在回文中）。如果是 s1 的一部分，但不匹配，则需要付费。

你的第二个 'please explain' 查看临时字符串的后半部分...它查看字符串 temp 中 j 的镜像位置处的字符是否落在属于 s1 的字符上并再次查看该位置的角色是否与其翻转相匹配...如果不匹配，则需要付出代价。

您基本上是在查看临时字符串中从字符串末尾开始到中间的字符。所以你先看第一个字符。如果字符来自 s1，则可以将其切换为最后一个字符。所以你只是增加成本。然后你看看 temp 中的最后一个字符。如果它来自 s1，那么它可以切换为任何第一个字符。所以你只是增加成本。现在增加 j，所以您正在查看第 2 个字符和倒数第 2 个字符，再次增加 j 您正在查看第 3 个字符和倒数第 3 个字符。等等等等....

如果在任何时候你不能交换前面的字符，也不能交换后面的字符..那么如果它们不匹配，就不可能有回文。

将 s1 转换为以 s2 为子串的回文

convert s1 to palindrome with s2 as its substring

c++

string

substring

palindrome

data-structures