⾯试编程题（字符串）1 字符串转整数
long long StrToIntCore(const char* str, bool minus);
enum Status {kValid = 0, kInvalid};
int g_nStatus = kValid;
int StrToInt(const char* str)
{
g_nStatus = kInvalid;
long long num = 0;
if(str != NULL && *str != '\0')
{
bool minus = false;
if(*str == '+')
str ++;
else if(*str == '-')
{
str ++;
minus = true;
}
if(*str != '\0')
{
num = StrToIntCore(str, minus);
}
}
return (int)num;
}
long long StrToIntCore(const char* digit, bool minus)
{
long long num = 0;
while(*digit != '\0')
{
if(*digit >= '0' && *digit <= '9')
{
int flag = minus ? -1 : 1;
num = num * 10 + flag * (*digit - '0');
if((!minus && num > 0x7FFFFFFF)
|| (minus && num < (signed int)0x80000000))
{
num = 0;
break;
}
digit++;
}
else
{
num = 0;
break;
}
}
if(*digit == '\0')
{
g_nStatus = kValid;
}
return num;
}
2字符串基本操作函数原型
int strlen(const char * str)
{
assert(str!=NULL);
int len = 0;
while((*str++) !=‘\0’)
len++;
return len;
}
int strcmp(const char* str1,const char* str2)
{
assert(str!=NULL && str2!=NULL);
int ret = 0;
while(!(ret = *(unsigned char*)str1-*(unsigned char*)str2)&& *str)
{
str1++;
str2++;
}
if(ret<0)    ret = -1;
else if(ret > 0)    ret = 1;
return    ret;
}
char * strcat(char *strDest,const char *strSrc)
{
char * address = strDest;
assert((strDest!=NULL) && (strSrc != NULL));
while(*strDest)
{
strDest++;
}
while(*strDest++ = *strSrc++);
return address;
}
char *  strcpy(char* strDest,const char * strSrc)
{
assert(strDest!= NULL && strSrc !=NULL);
char * strD = strDest;
while((*strDest++=*strSrc++)!='\0');
return strD;
}
3字符串匹配 KMP
int kmp_search(const char* src,int slen,const char* patn,int plen,const int * nextval,int pos) {
int i =pos , j=0;
while(i<slen && j<plen)
{
if(j==-1 || src[i]==patn[j]){++i;++j;}
else
{
j = nextval[j];
}
}
if(j>=plen) return i-plen;
else return -1;
}
void get_nextval(char const* ptrn,int plen,int *nextval)
{
int i = 0;
nextval[i] = -1;
int j=-1;
while(i<plen-1)
{
if(j==-1||ptrn[i]==ptrn[j]){++i;++j;nextval[i]=j;}
else
j=nextval[j];
}
}
//改进
void get_nextval(char const* ptrn,int plen,int *nextval)
{
int i = 0;
nextval[i] = -1;
int j=-1;
while(i<plen-1)
{
if(j==-1||ptrn[i]==ptrn[j])
{
++i;
++j;
if(ptrn[i]!=ptrn[j])
nextval[i]=j;
else
nextval[i]=nextval[j];
}
else
j = nextval[j];
}
}
//最基础的BF算法
char* strFind(const char*str,const char* substr)
{
assert(str!=NULL && substr!=NULL );
int m = strlen(str);
int n = strlen(substr);
if(m < n)
return NULL;
for(int i=0; i<=m-n;i++)
{
for(int j=0;j<n;j++)
{
if(str[i+j]!=substr[j])
break;
}
if(j==n)
return str+i;
}
return NULL;
字符串函数编程题}
4 最长回⽂⼦串Manacher
/*最长回⽂⼦串长度
Manacher算法
*/
void Manacher(char* str)
{
int len = strlen(str);
int i,id,maxid = 0;
int newstr_len =0;
newstr[newstr_len++] = '@';
for (i = 0; i < len; i++){
newstr[newstr_len++] = '#';
newstr[newstr_len++] = str[i];
}
newstr[newstr_len++] = '#';
newstr[newstr_len++] = '$';
int * p = new int[newstr_len];
for(i=1;i<newstr_len-1;i++)
{
if(maxid > i)
p[i] = min(p[2*id-i],maxid-i);
else
p[i] = 0;
while(newstr[i+1+p[i]]==newstr[i-1-p[i]])
p[i]++;
if(p[i]+i>maxid)
{
maxid = p[i]+i;
id = i;
}
}
int maxlen = 0;
int centerIndex = 0;
for (i = 1; i<newstr_len-1;i++){
if(p[i] > maxlen)
{
maxlen = p[i];
centerIndex = i;
}
}
delete[] p;
printf("%d:",maxlen);
for(int i=(centerIndex-1-maxlen)/2;i<=maxlen;i++)        putchar(str[i]);
putchar('\n');
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。