如何在不使用輔助字串的情況下找到 const char 字串中最長單詞的長度？
#include <stdio.h>
int longest(const char *str) {
int max = 0, prev = 0, final_max = 0;
while (*str != '\0') {
prev = max;
max = 0;
while (1) {
if (*str != ' ')
max ;
str ;
if (*str == ' ')
break;
}
if (prev > max)
final_max = prev;
str ;
}
return final_max;
}
void main() {
const char str[] = "Longest word in string";
printf("%d", longest(str));
}
這列印4為最長單詞的長度。你能幫我解決這個問題嗎？
uj5u.com熱心網友回復：
您可以在線性時間內找到最長的單詞。這肯定是最優的，因為任何演算法都必須至少處理每個字符一次。
基本思想是遍歷字串的每個字符，跟蹤最后一個空格（或任何其他單詞分隔符）的位置。每次當前字符是空格時，我們都會更新答案。
請注意，我們需要在末尾添加一個額外的檢查，以防最長單詞是字串中的最后一個（因此后面不一定要跟一個空格）。
這是一個簡單的實作：
#include <stdio.h>
size_t longest(const char *str) {
size_t i, last=-1, ans=0;
for (i = 0; str[i] != '\0'; i )
if (str[i] == ' ') {
if (ans < i-last) ans = i-last-1;
last = i;
}
if (ans < i-last) ans = i-last-1;
return ans;
}
void main(){
printf("%zu\n", longest("Longest word in string")); // 7
}
uj5u.com熱心網友回復：
簡單地走一次字串。
走過空白處后，注意單詞的開頭。遍歷一個單詞后，記下它的長度并與當前最長的長度進行比較。這樣做直到檢測到空字符。
使用size_t, 而不是int處理長字串。
通過 an 訪問字符unsigned char*以正確使用isspace().
例子：
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
size_t longest1(const char *str) {
// Print up to 30 characters of str - for debug
printf("<%.30s> ", str);
size_t longest_length = 0;
// Access the string as if it had unsigned chars.
const unsigned char *s = (const unsigned char*) str;
while (isspace(*s)) {
s ;
}
while (*s) {
const unsigned char *start = s;
do {
s ;
} while (!isspace(*s) && *s);
size_t length = (size_t) (s - start);
if (length > longest_length) {
longest_length = length;
}
while (isspace(*s)) {
s ;
}
}
return longest_length;
}
測驗
int main(void) {
printf("%zu\n", longest("Longest word in string"));
printf("%zu\n", longest(""));
printf("%zu\n", longest(" "));
printf("%zu\n", longest(" "));
printf("%zu\n", longest("a"));
printf("%zu\n", longest(" b"));
printf("%zu\n", longest("c "));
printf("%zu\n", longest("dd e"));
printf("%zu\n", longest(" ff g"));
printf("%zu\n", longest("hh i "));
printf("%zu\n", longest("j kk"));
printf("%zu\n", longest(" l mm"));
printf("%zu\n", longest("n oo "));
char *buf = malloc(INT_MAX * 2u);
if (1 && buf) {
memset(buf, 'x', INT_MAX * 2u - 1);
buf[INT_MAX * 2u - 1] = '\0';
printf("%zu\n", longest(buf));
free(buf);
}
}
輸出
<Longest word in string> 7
<> 0
< > 0
< > 0
<a> 1
< b> 1
<c > 1
<dd e> 2
< ff g> 2
<hh i > 2
<j kk> 2
< l mm> 2
<n oo > 2
<xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx> 4294967293
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/436453.html
下一篇：正則運算式檢測包含特殊字符的字串