Item A similarity detection
B - initial capital
C case conversion
D digital inversion
E - delete word suffix
F - judge whether the string is palindrome
G - basic data structure - stack (1)
H - dictionary order
I - verify substring
J - substring lookup
K - cut cloth strip
L - longest palindrome substring
Item A similarity detection
Idea: Violence
code:
#include<iostream>
using namespace std;
int count=0;
int main()
{
string s1,s2;
getline(cin,s1);//Read two strings.
getline(cin,s2);
int l=(s1.size()>s2.size())?s2.size():s1.size();//Compare the length of the two strings and assign the longest to l
int a[l];
for(int i=0;i<l;i++)
{
if(s1[i]==s2[i])
a[i]=1;
else
a[i]=0;
}
for(int i=0;i<l;i++)
if(a[i]==1)
cout<<i+1<<" ";
}
B - initial capital
Idea: Violence
code:
***Solution 1:***
#include<iostream>
using namespace std;
int main(){
string a;
int i;
getline(cin,a);
int l=a.size();
if(a[0]>=97&&a[0]<=122)a[0]-=32;
for(i=0;i<=l;i++){
if(a[i]>=97&&a[i]<=122&&a[i-1]==' ')
a[i]=a[i]-32;
}
cout<<a<<endl;
return 0;
}
**Solution 2:**
#include <stdio.h>
#include <stdlib.h>
int islittle (char ch);
int main()
{
char str[100];
gets(str);
int i;
for(i = 0;str[i] != '\0';i++)
{
if(str[i] == ' ' && str[i+1] != ' ')///One is missing if it starts with a letter
{
if(islittle(str[i+1]))///If lowercase
str[i+1] -= 32;
}
}
if (str[0] != ' ' &&islittle(str[0]))
str[0] -= 32;
printf("%s",str);
return 0;
}
int islittle(char ch)
{
if(ch>='a' && ch <= 'z')
return 1;
else
return 0;
}
C case conversion
Idea: Violence
code:
#include<iostream>
#include<string.h>
using namespace std;
int main()
{
char s[81];
int n=0;
while(scanf("%s", s) == 1)//Enter multiline string
{
int len=strlen(s);
for (int i = 0; i <len; i++) {
if ('a' <=s[i] && s[i] <= 'z') { // Determine whether it is lowercase
s[i] = s[i] - ('a' - 'A'); // Convert to uppercase
}
cout << s[i];
}cout<<endl;
}
}
D digital inversion
Idea: simulation
code
Solution 1:
#include <stdio.h>
#include <string.h>
int main()
{
char s[100];
gets(s);
int n,f=0,t;
n=strlen(s)-1; //Count the length of the string. Note that the subscript starts from 0 and the value should be minus 1
while(s[n]=='0') //Calculate the first non '0' position
{
n--;
t=n;
}
if(s[0]=='-') //Symbolic judgment
{
f=1;
printf("-");
}
for(int i=n;i>=1;i--) //Output in reverse order from non '0' position
{
printf("%c",s[i]);
}
if(f==0) //Separate output
{
printf("%c",s[0]);
}
return 0;
}
Solution 2:
#include<iostream>
using namespace std;
int main (){
int n;
int s=0;
cin>>n;
while(n!=0){
int ge=n%10;//Redefine and assign the last bit of n
s=s*10+ge;// Core code
n/=10;//Remove the last bit of n
}
cout<<s;//Output results
return 0;
}
E - delete word suffix
Idea: direct judgment
code:
#include<iostream>
#include<string.h>
using namespace std;
int main()
{
char s[33];
gets(s);
int l=strlen(s);
if(s[l-1]=='r'&&s[l-2]=='e') s[l-2]='\0';
if(s[l-1]=='y'&&s[l-2]=='l') s[l-2]='\0';
if(s[l-1]=='g'&&s[l-2]=='n'&&s[l-3]=='i') s[l-3]='\0';
cout<<s;
}
F - judge whether the string is palindrome
Idea: simulation
code:
Solution 1:
#include<iostream>
#include<string>
using namespace std;
int main()
{
string s;
cin>>s;
char a[100];
int n=0;
for(int i=0;i<s.size();i++ )
{
a[++n]=s[i];//Assign to array a
}
for(int i=0;i<s.size();i++)
{
if(a[n]!=s[i])
{
cout<<"no";
return 0;
}
n--;
}
cout<<"yes";
}
Solution 2:
#include <stdio.h>
#include <math.h>
#include <string.h>
int main()
{
char a[100];
int i, j;
gets(a);
j = strlen(a) - 1; //Assign the length of the string after - 1 to j
for (i = 0; i < j; i++, j--) //Gradually compare the characters from both sides to see if they are the same
if (a[i] != a[j]) break;
if (a[i] == a[j])
printf("yes");
else printf("no");
return 0;
}
G - basic data structure - stack (1)
Idea: firstly, use the stack structure to save the relevant symbols, and constantly eliminate the paired symbols to judge whether the last is empty. Note that the input can be blank
code:
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll maxn=1e5+100;
char str[1000];
int judge(char c)
{
if(c=='{'||c=='}')return 1;
if(c=='('||c==')')return 1;
if(c=='['||c==']')return 1;
return 0;
}
int main()
{
while(cin.getline(str,1000,'\n'))
{
stack <char> st;//Stack st
ll l=strlen(str);
for(int i=0;i<l;i++)
{
if(judge(str[i]))
{
if(st.empty())//Is it an empty stack
{
st.push(str[i]);//Stack array elements
}
else
{
char c=st.top();//The top of the stack
st.pop();//Out of stack
if(str[i]=='}')
{
if(c!='{')
{
st.push(c);
st.push(str[i]);
}
}
else if(str[i]==']')
{
if(c!='[')
{
st.push(c);
st.push(str[i]);
}
}
else if(str[i]==')')
{
if(c!='(')
{
st.push(c);
st.push(str[i]);
}
}
else
{
st.push(c);
st.push(str[i]);
}
}
}
}
if(st.empty())//All parentheses match successfully
{
printf("yes\n");
}
else
{
printf("no\n");
}
}
return 0;
}
H - dictionary order
Idea: you can compare functions directly with strings.
code:
#include<stdio.h>
#include<string.h>
#include<math.h>
int main()
{
char s1[10000];
char s2[10000];
gets(s1);
gets(s2);
int t;
t=strcmp(s1,s2);
if(t<0)
{
printf("YES");
}
else if(t>0)
{
printf("NO");
}
}
I - verify substring
Idea: firstly, the scope is relatively small, and violent backtracking can be carried out. Here, kmp is used to solve it, which is a review. Direct application of kmp.
code:
#include<iostream>
#include<string>
using namespace std;
int main()
{
string a,b;
getline(cin,a);
getline(cin,b);
if(a.find(b)!=string::npos )//Find a match. When a.find(b)==string::npos, the string B does not exist in string a.
cout<<b<<" is substring of " <<a;
else if(b.find(a)!=string::npos)
cout<<a<<" is substring of " <<b;
else
cout<<"No substring";
}
J - substring lookup
Idea: template topic, direct application of kmp algorithm
code:
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
using namespace std;
int s[1000100],l1,l2;
char a[1000100],b[1000100];
void get_next()
{
int i=0,j=-1;
s[0]=-1;
while(i<l2)
{
if(j==-1||b[i]==b[j])
{
i++;
j++;
s[i]=j;
}
else
j=s[j];
}
}
void kmp()
{
int i=0,j=0;
int ans=0;
while(i<l1)
{
if(j==-1||a[i]==b[j])
{
++i;
++j;
}
else
j=s[j];
if(j==l2)
{
j=s[j];
ans++;
}
}
printf("%d\n",ans);
}
int main()
{
scanf("%s %s",a,b);
l1=strlen(a);
l2=strlen(b);
if(l2>l1)
printf("0\n");
get_next();//Call two functions
kmp();
}
K - cut cloth strip
Idea: oj the original question, direct violence simulation can also be done, that is, when the matching is successful, no backtracking is carried out, so that the variable becomes zero, and the rest is similar to the previous question
code:
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
#define maxn 1010
char s[maxn];
char t[maxn];
int next[maxn];
int a,b;
void get_next()
{
next[0]=0;
int i=1,j=0;
while(i<b)
{
if(t[i]==t[j])
{
next[i++]=++j;
}
else if(!j){
i++;
}
else
{
j=next[j-1];
}
}
}
int kmp()
{
int i=0,j=0,ans=0;
while(i<a&&j<b)
{
if(s[i]==t[j])
{
i++;j++;
}
else if(!j)
{
i++;
}
else{
j=next[j-1];
}
if(j==b)
{
j=0;ans++;
}
}
return ans;
}
int main()
{
while(scanf("%s",s))
{
if(strcmp(s,"#")==0)
{
break;
}
scanf("%s",t);
a=strlen(s);
b=strlen(t);
get_next();
printf("%d\n",kmp());
}
return 0;
}
L - longest palindrome substring
Idea: for the classic topic, dynamic programming is used, in which the determined results are used to push. The cycle of the first layer is inverted and the second layer is positive. The reason is that the result of dp[i][j] is derived from dp[i+1][j-1]. Therefore, the first layer needs to push the large I value first, and the second layer j needs the small j value
code:
#include<bits/stdc++.h>
#include<string.h>
#include<cmath>
using namespace std;
char *longestPalindrome(char * s)
{
int n = strlen(s);
int dp[n][n];
int l, i;
static char ans[100];
for(i=0; i<n; i++)
for(l=0; l<n; l++)
dp[i][l]=0;
for(l=0; l<n; l++) //Substring length
{
for(i=0; i+l<n; i++) //Substring start position
{
int j = i+l; //Substring end position
if(l==0)
dp[i][j]=1;
else if(l==1)
dp[i][j]=(s[i]==s[j]);
else
{
dp[i][j] = ((s[i]==s[j]) && dp[i+1][j-1]);
}
if(dp[i][j] && l+1>strlen(ans))
{
strncpy(ans,s+i,l+1);
}
}
}
return ans;
}
int main()
{
char str[1010];
int count;
gets(str);
cout<<strlen(longestPalindrome(str));
}