编程题车站的问题

我直接输出结果，没写过程，还通过了10%

#include "bits/stdc++.h" using namespace std; int main() { string mn,a,b; while(cin>>mn>>a>>b) { int lena=a.size(); int lenb=b.size(); string nm=mn; reverse(mn.begin(),mn.end()); bool ntom=false,mton=false; if(nm.find(a)!=string::npos) { int pos=nm.find(a); string t=nm.substr(pos+lena); // cout<<"nm:"<<t<<endl; if(t.find(b)!=string::npos) ntom=true; } if(mn.find(a)!=string::npos) { int pos=mn.find(a); string t=mn.substr(pos+lena); // cout<<"mn:"<<t<<endl; if(t.find(b)!=string::npos) mton=true; } if(ntom&&!mton) cout<<"forward"<<endl; if(mton&&!ntom) cout<<"backward"<<endl; if(ntom&&mton) cout<<"both"<<endl; if(!ntom&&!mton) cout<<"invalid"<<endl; } return 0; }

60%

python 过了70%，不知道剩下的30%什么情况，难道一个车站的旗子可以看两次？》

好机智的解答🤔

这个问题，我一开始用KMP算法正一遍，反一遍找匹配字符串后对应输出的啊 ，而且第二次看到的旗帜一定要在第一次看到的旗帜后面这点也考虑到了，数组越界也考虑了，但是提示Wrong Answer，好像是说全部未通过，示例都能通过至少也不该是0%吧，这里的KMP算法通过了牛客网的测试用例的函数 import java.util.Scanner; public class Main { public static int[] getPMT(char[] b,int lenb){ int[] arr=new int[lenb]; arr[0]=0; int i=0,j=-1; while(i<lenb-1){ if(j==-1 || b[i]!=b[j]){ i++; j++; if(b[i]==b[j]){ arr[i]=j+1; } else{ arr[i]=0; j=-1; } } else{ i++; j++; if(b[i]!=b[j]){ i--; j=-1; } else{ arr[i]=j+1; } } } return arr; }          public static int findAppearance(String A, int lena, String B, int lenb,int mark) {         // write code here         if(lena<lenb)return -1; char[] a=A.toCharArray(); char[] b=B.toCharArray(); int[] pmt=getPMT(b,lenb); //new int[lenb];  //部分匹配表 int i=mark;  //左对齐下标 int j=0;  //内标 while(i<=lena-lenb){ while(j<lenb){ if(a[i]!=b[j]){ if(j==0)i++; else{ i-=pmt[j-1]; } j=0; break; } else{ i++; j++; if(j==lenb)return i-lenb;  //返回对齐的字符串头位置 } } } return -1;  //无匹配则返回-1     }          public static int check(int nA,int nB,int nA2,int nB2,int lA){     if((nB-nA)>=lA && nA!=-1 && nB!=-1){ if((nB2-nA2)>=lA && nA2!=-1 && nB2!=-1){ return 3;  //表示both } else{ return 1;  //表示forward } }     else if((nB2-nA2)>=lA && nA2!=-1 && nB2!=-1){     return 2;  //表示backward     }     return 4;  //表示invalid     } public static void main(String[] args) {   Scanner sc=new Scanner(System.in); String C=sc.nextLine();  //正序路径 int lC=C.length(); char[] c=C.toCharArray(); String C2=""; for(int i=0;i<lC;i++){ C2+=c[lC-1-i]; } String A=sc.nextLine(); String B=sc.nextLine(); int nA,nB; int nA2,nB2; nA=findAppearance(C,lC,A,A.length(),0); nB=findAppearance(C,lC,B,B.length(),nA+A.length()); nA2=findAppearance(C2,lC,A,A.length(),0); nB2=findAppearance(C2,lC,B,B.length(),nA2+A.length()); int re=check(nA,nB,nA2,nB2,A.length()); if(re==1)System.out.println("forward"); else if(re==2)System.out.println("backward"); else if(re==3)System.out.println("both"); else if(re==4)System.out.println("invalid");     }   }

50% 思路是计算比较最长公共子串的长度 #include<iostream> #include<string> #include<vector> #include<algorithm> using namespace std; //是否存在子串 int findLongestSize(string A, string B, int&endindex) { int n=A.size(); int m=B.size(); vector<vector<int> > matrix(n,vector<int>(m,0)); int res=0; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(A.at(i)==B.at(j)) { if(i==0||j==0) matrix[i][j]=1; else matrix[i][j]=matrix[i-1][j-1]+1; if(res<matrix[i][j]) { res=matrix[i][j]; endindex=i; } } } } return res; } int main() { string line; //string x="nihao"; //cout<<x.substr(3); string a,b; string output4[4]={"invalid","forward","backward","both"}; while(cin>>line) { int res=0;//0-invalid 3both cin>>a>>b; if(a.size()+b.size()>line.size()) { cout<<output4[res]<<endl; continue; } //isforward int lcs1=0; int lcs2=0; int endindex=0; lcs1=findLongestSize(line,a,endindex); if(line.size()-endindex>b.size()) { lcs2=findLongestSize(line.substr(endindex+1),b,endindex); if(lcs1+lcs2==a.size()+b.size()) res=1; } //isbackward string rline=line; reverse(rline.begin(),rline.end()); int lcs3=0; int lcs4=0; endindex=0; lcs3=findLongestSize(rline,a,endindex); if(rline.size()-endindex>b.size()) { lcs4=findLongestSize(line.substr(endindex+1),b,endindex); if(lcs3+lcs4==a.size()+b.size()) { if(res) res=3; else res=2; } } cout<<output4[res]<<endl; } return 0; }

怎么说呢……这个题我卡了个bug,当我发现可以import re的时候，直接用正则就AC了……

%100通过，用正则表达式 import java.util.Scanner; public class App { public static void main(String[] args) { Scanner sc=new Scanner(System.in); while(sc.hasNext()){ String str=sc.next(); String s1=sc.next(); String s2=sc.next(); boolean a=false,b=false; if(str.matches(".*"+s1+".*"+s2+".*")) a=true; if(str.matches(".*"+new StringBuilder(s2).reverse().toString()+".*" +new StringBuilder(s2).reverse().toString()+".*")) b=true; if(a&&b) System.out.println("both"); else if(a) System.out.println("forward"); else if(b) System.out.println("backward"); else System.out.println("invalid"); } } }

int main() {     int len,len1,len2;     while(scanf("%s",sa) != EOF) {         scanf("%s",s1);         scanf("%s",s2);         len=strlen(sa);         len1=strlen(s1);         len2=strlen(s2);         for (int i=0;i<len;i++) sb[i]=sa[len-1-i];         for (int i=0;i<len1;i++) s3[i]=s1[len1-1-i];         for (int i=0;i<len2;i++) s4[i]=s2[len2-1-i];         GetNextval(s1);         int a1 = KmpSearch(sa,s1);         int a2 = KmpSearch(sb,s1);         GetNextval(s4);         int b1 = KmpSearch(sb,s4);         int b2 = KmpSearch(sa,s4);         bool flag1=false;         bool flag2=false;         if (a1!=-1 && b1!=-1 && a1+len1-1 < len-b1-len2) flag1=true;         if (a2!=-1 && b2!=-1 && a2+len1-1 < len-b2-len2) flag2=true;         //cout << a1 << len-b1-len2 << a2 << len-b2-len2 << endl;         if (flag1 && flag2) {             printf("both\n");             continue;         }         if (!flag1 && !flag2) {             printf("invalid\n");             continue;         }         if (flag1) {             printf("forward\n");         }         if (flag2){             printf("backward\n");         }      }     return 0; }

这道题我只通过了70%。。。没有完全AC，会有分数吗？

过了90%，还有10%不知道是啥情况

只过了60%， 帮忙分析下，写的有点挫

hint说n,m站没有旗帜

题目有说车站没有旗子，所以最后一面旗子不可能在车站看到的。。