3127. 字串间距

题面 统计数据 讨论
deerbean
6 年，4 月前

理解题意是关键，然而这并不容易，只能靠多猜几种可能
在这里给一个案例帮助理解：
belongto
us
usxxxbelongtoxxxbelongtoxxxbelongtoxxxbelongto12
case # :
36
另外，要注意对重合的判定，且重合时直接计算结果非0，但从测试数据来看，重合时应特判为0。

回复
Gottfried_Leibniz
4 年，2 月前

EOJ的字符串类型的题目居然这么多是C风格，
String它不香吗
我觉得C语言还不如Brainfuck
那才算模拟计算机的内存操作(逃
//另外这道题测试点比较弱，还有一些情形，测试点是没有涵盖的

#include<iostream>
#include<string>

using namespace std;

int32_t main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(0);

    int32_t T,f1,f2,rf1,rf2;
    string s1,s2,s3;
    cin >> T;
    cin.get();
    for(int32_t i = 0; i < T; i++){
        cout << "case #" << i << ":\n";
        getline(cin,s1);
        getline(cin,s2);
        getline(cin,s3);

        f1 = s3.find(s1);
        rf1 = s3.rfind(s1);
        f2 = s3.find(s2);
        rf2 = s3.rfind(s2);

        string a(s1);
        string b(s2);

        bool sub1 = (s2.find(s1) != string::npos) && (s1 != s2);
        bool sub2 = (!sub1) && (s1.find(s2) != string::npos) && (s1 != s2);

        if(f1 == string::npos || f2 == string::npos || (s1 == s2 && f1 == rf1) || ((sub1) && (f1 == rf1)) || ((sub2) && (f2 == rf2))){
            cout << 0 << endl;
        }else{
            cout << max(rf1 - f2 - (int32_t)s2.size(), rf2 - f1 - (int32_t)s1.size()) << endl;
        }
    }
}
回复
aiden
4 年，2 月前

用strrstr()查找给定字符串最右侧的子串

#include <stdio.h>
#include <string.h>

char *strrstr(const char *s1, const char *s2);

int main()
{
    int t;
    scanf("%d ", &t);
    for (int z = 0; z < t; z++)
    {
        char s1[81], s2[81], s3[81];
        scanf("%s", s1);
        scanf("%s", s2);
        scanf("%s", s3);
        char* idx1 = NULL, *idx2 = NULL;
        idx1 = strstr(s3, s1);
        idx2 = strrstr(s3, s2);
        printf("case #%d:\n", z);
        if (idx1 == NULL || idx2 == NULL || idx1 == idx2)
            printf("0\n"); 
        else if (idx2 < idx1)
            printf("%d\n", strrstr(s3, s1) - strstr(s3, s2) - strlen(s2));
        else if (idx2 > idx1)
            printf("%d\n", idx2 - idx1 - strlen(s1));
    }
    return 0;
}

char *strrstr(const char *s1, const char *s2)
{
    char *tmp = strstr(s1, s2);
    char *ret = NULL;
    while (1)
    {
        if (tmp != NULL)
        {
            ret = tmp;
        }
        else
            break;
        tmp = strstr(tmp + strlen(s2), s2);
    }
    return ret;
}
回复
wjwjwj
4 年，1 月前

不是很严谨，但是能AC
int main() {
int t;
cin >> t;
for (int p = 0; p < t; p++) {
string str1, str2, s;
cin >> str1 >> str2 >> s;
int f1 = 0;
int max = 0;
while ((f1 = s.find(str1, f1)) != string::npos) {
int f2 = 0;
while ((f2 = s.find(str2, f2)) != string::npos) {
if (max < abs(f2 - f1)) max = abs(f2 - f1);
f2++;
}
f1++;
}
if (max != 0) max -= min(str1.size(), str2.size());
printf(“case #%d:\n%d\n”, p, max);
}
}

回复
10165101115
7 年，1 月前

我觉得题目有点误导性呀
说距离是非负整数，但是正确代码重叠时输出了负数呀？？

回复
10165101122
7 年，1 月前

总算是ac掉了

include

include

include

int Lookfor_max(char s[],char m[])
{
int a,b,flag;
int max=0;
a=strlen(s);
b=strlen(m);
int i,j=0,trace=0;
for(i=0;i<b;++i)
{
trace=i; flag=i;
while(m[trace]==s[j])
{
++trace;++j;
if(j==a)
{ max=flag+1;
break;
}
}
j=0;
}

return max;

}
int Lookfor_min(char s[],char m[])
{
int a,b,flag;
int min=0;
a=strlen(s);
b=strlen(m);
int i,j=0,trace=0;
for(i=0;i<b;++i)
{
trace=i; flag=i;
while(m[trace]==s[j])
{
++trace;++j;
if(j==a)
{
min=flag+1;
break;
}
}
if(j==a)
{
break;
}
j=0;
}
return min;
}

void solve(int i)
{
char s1[500],s2[500],s[500];
scanf(“%s”,s1);
scanf(“%s”,s2);
scanf(“%s”,s);

int max1=Lookfor_max(s1,s);
int max2=Lookfor_max(s2,s);
int min1=Lookfor_min(s1,s);
int min2=Lookfor_min(s2,s);

printf("case #%d:\n",i);
if(max1!=0&&min1!=0&&max2!=0&&min2!=0)
{
    if(max1==min1&&max2==min2&&max1==max2)
    {
        printf("0\n");
    }
    else{
    int flag1=max1-min2-strlen(s2);
    int flag2=max2-min1-strlen(s1);
    if(flag1>=flag2)
    {
        printf("%d\n",flag1);
    }
    else{
        printf("%d\n",flag2);
    }}
}
else
{
    printf("0\n");
}

}

int main()
{
int T;
scanf(“%d”,&T);
int i;
for(i=0;i<T;++i)
{
solve(i);
}
}

//先前一直把两字符串重合的情况忽略了

回复
三七茧茧
6 年，1 月前

受益匪浅

回复
Li Dao
7 年，2 月前

来自渣渣的一点提示

include

using namespace std;
int T;
string s1,s2,s;

int Find(const string& big,const string& small,int dir)
{
if(big.find(small)==-1) return -1;

if(dir==0) return big.find(small)+small.length()-1;
else return big.rfind(small);
}
void solve()
{
cin>>s1>>s2>>s;
int ans=0;

if(Find(s,s2,0)==-1 || Find(s,s1,0)==-1)
{
cout<<0<<endl;
return;
}

int tmp1=Find(s,s2,1)-Find(s,s1,0)-1;
int tmp2=Find(s,s1,1)-Find(s,s2,0)-1;

ans=max(max(tmp1,tmp2),ans);
cout<<ans<<endl;
return;
}

int main()
{
scanf(“%d”,&T);
for(int step=0;step<T;step++)
{
printf(“case #%d:\n”,step);
solve();
}
return 0;
}

用好find和rfind，写起来很快

回复
Master X
6 年，2 月前

这题就是要想好算法，然后实现就行，可以避免出现负数的……
可以先存好s1,s2出现位置，然后遍历比较即可。

include

using namespace std;
int fin(char s1[],char s[],int a[])
{
int l1=strlen(s1);
int l2=strlen(s);
int num=0;
int n=0;
for(int i=0;i<l2;i++)
for(int t=i,j=0;t>T;
for(int i1=0;i1<T;i1++)
{char s1[81],s2[81],s[81];
int a[100]={0};
int b[100]={0};
scanf(“%s”,s1);
scanf(“%s”,s2);
scanf(“%s”,s);
int l1=strlen(s1);
int l2=strlen(s2);
int n1=fin(s1,s,a);
int n2=fin(s2,s,b);
int num=0;
for(int i=0;i<n1;i++)
for(int j=0;j<n2;j++)
{
if(a[i]<b[j]) num=max(num,b[j]-a[i]-l1);
else num=max(num,a[i]-b[j]-l2);

    }
    printf("case #%d:\n",i1);
cout<<num<<endl;}

}

回复
10175101290
6 年，1 月前

要注意S1或者s2不在S中，或者两者都不在S中的情况。这时候要输出0。
可以通过将它们的位置信息都始化为-1来判断是否发生了这种情况。

回复
10175101173
6 年，1 月前

void solve() {
string s1;
string s2;
string str;
cin >> s1 >> s2 >> str;
int dis = 0;
int dis1 = str.rfind(s2) - str.find(s1) - s1.size();
int dis2 = str.rfind(s1) - str.find(s2) - s2.size();
dis1>dis2 ? dis = dis1: dis =dis2;
if (str.rfind(s2) == -1 || str.find(s1) == -1) dis = 0;
if(s1==str||s2==str)dis=0;
cout << dis << endl;
}苟一段代码，提交的时候基本把所有的雷区都踩了一遍,还是自己太菜···

回复
徐摆渡
5 年，2 月前

这道题坑点真的好多..

回复
Suzuki_Yuuta
3 年，7 月前 
void solve() {
    string x, y, line;
    cin >> x >> y >> line;
    int x_index = line.find(x), y_index = line.rfind(y);
    int res = 0;
    if (x_index == -1 || y_index == -1) {
        res = 0;
    } else {
        if (x_index == y_index) {
            res = 0;
        } else if (x_index > y_index) {
            x_index = line.rfind(x); y_index = line.find(y);
            res = x_index - y_index - y.length();
        } else {
            res = y_index - x_index - x.length();
        }
    }
    cout << res << endl;
}
回复
LzQuarter
5 年，7 月前 
#include<iostream>
#include<algorithm>
using namespace std;
typedef struct _{
    int left;
    int right;
}mark;

int match(string s, string sub, mark arr[]){
    int cnt = 0;
    int slen = s.length();
    int sublen = sub.length();
    for(int i = 0; i < slen; i++){
        int matched = 1;
        for(int j = 0; j < sublen; j++){
            if(i + j >= slen || s[i + j] != sub[j]){
                matched = 0;
                break;
            }
        }
        if(matched){
            arr[cnt].left = i;
            arr[cnt].right = i + sublen - 1;
            cnt++;
        }
    }
    return cnt;
}

int fun(mark a, mark b){
    return a.left < b.left;
}

int dis(mark a, mark b){
    int dis1, dis2;
    dis1 = a.left - b.right - 1;
    dis2 = b.left - a.right - 1;
    if(dis2 > dis1){
        dis1 = dis2;
    }
    if(dis1 < 0){
        dis1 = 0;
    }
    return dis1;
}

int main(){
    int T;
    cin >> T;
    for(int t = 0; t < T; t++){
        cout << "case #" << t << ":" << endl;
        string s1, s2, s;
        cin >> s1 >> s2 >> s;
        mark s1ins[81];
        mark s2ins[81];
        int s1insnum = match(s, s1, s1ins);
        int s2insnum = match(s, s2, s2ins);
        if(s1insnum == 0 || s2insnum == 0){
            cout << "0" << endl;
        }
        else{
            sort(s1ins, s1ins + s1insnum, fun);
            sort(s2ins, s2ins + s2insnum, fun);
            int dis1 = dis(s1ins[0], s2ins[s2insnum - 1]);
            int dis2 = dis(s2ins[0], s1ins[s1insnum - 1]);
            if(dis2 > dis1){
                dis1 = dis2;
            }
            cout << dis1 << endl;
        }
    }
    return 0;
}
回复
10185101158
4 年，11 月前

include

include

include

int find_front(char s1,char s2);
int find_back(char s1,char s2);
int main()
{
int t,w=0;
scanf(“%d”,&t);
getchar();
while(t–>0)
{
char s1[81];
char s2[81];
char s[81];
int front1,back1,front2,back2;
gets(s1);
gets(s2);
gets(s);
front1=find_front(s,s1);
back1=find_back(s,s2);
front2=find_front(s,s2);
back2=find_back(s,s1);
printf(“case #%d:\n”,w++);
if(back1-front1>=0&&front1!=0&&back1!=0)
printf(“%d\n”,back1-front1);
else if(back2-front2>=0&&front2!=0&&back2!=0)
printf(“%d\n”,back2-front2);
else
{
printf(“0\n”);
}
}
return 0;
}
int find_front(char s1,char s2)
{
int len1=strlen(s1);
int len2=strlen(s2);
int i,k,flag=0;
for(i=0;i<len1;i++)
{

    if(s1[i]==s2[0])
    {
        int f=i;
        int f2=0;
        for(k=i;k<f+len2;k++)
        {
            if(s1[k]==s2[f2++])
                flag=1;
            else
            {
                flag=0;
                break;
            }
        }
    }
    if(flag==1)
        break;
}
if(flag==0)
    return 0;
else
    return i+len2;

}
int find_back(char s1,char s2)
{
int len1=strlen(s1);
int len2=strlen(s2);
int i,k,flag=0;
for(i=len1-1;i>=0;i–)
{
if(s1[i]==s2[len2-1])
{
int f=i;
int f2=len2-1;
for(k=f;k>f-len2;k–)
{
if(s1[k]==s2[f2–])
{
flag=1;
}
else
{
flag=0;
break;
}
}
}
if(flag==1)
break;
}
if(flag==0)
return 0;
else
return i-len2+1;
}
​

回复
10165102108
7 年，1 月前

不知道哪里有问题

include

include

int main()
{
int t,T;
scanf(“%d”,&T);
for(t=0; t<T; t++){
char s1[80]={0},s2[80]={0},s[80]={0};
scanf(“%s%s%s”,s1,s2,s);
int n1,n2,n;
n1=strlen(s1);
n2=strlen(s2);
n=strlen(s);
int i,j,k,m1=-1,m2=-1;
for(i=0; i<n; i++){
for(j=0,k=i; j<n1; j++,k++){
if(s[k]!=s1[j]) break;
}
if(j==n1) {
m1=k;
break;
}
}
for(i=0; i=0; j–,k–){
if(s[k]!=s2[j]) break;
}
if(j<0) {
m2=++k;
break;
}
}
printf(“case #%d:\n”,t);

    if(m1==-1||m2==-1||m1>m2) printf("0\n");
    else printf("%d\n",m2-m1);


}
return 0;

}

这道题都有什么特殊情况啊？

回复
你当前正在回复 博客/题目
存在问题！

服务

首页 反馈 Polygon Wiki

开源

Github eJudge

关于我们

团队: @ultmaster, @zerol, @kblack.
联系方式: acmsupport@admin.ecnu.edu.cn