字串"/>
查找最长不重复字串
C++实现
输入:GongCheng
输出:GongChe :max length is 7, start from 1 char.
/*
* 查找最长不重复字串
* GC
* 2019-8-25
*/
#include<iostream>
using namespace std;
char* isRepeat(char* p1, char* p2){// 查找*p2是否在[p1,p2-1]中,即重复// 如果返回p1==p2,则表示未重复,否则返回重复位置while (*p1 != *p2) p1++;return p1;
}
void findNonRepeatStr(char* p, char* &start_pos, int& length){//p: 输入字符串首地址//stat_pos: 返回最长不重复字符串首地址//length: 最长不重复字符串长度char* p1=NULL, *p2=NULL;start_pos = p;length = 0;for (p2 = p + 1; *p2 != '\0'; p2++){if ((p1=isRepeat(p, p2)) != p2){//出现了重复字符串int tmp_len = p2 - p;if (tmp_len > length){length = tmp_len;start_pos = p;}p = p1 + 1;}}if (p2 - p > length){length = p2 - p;start_pos = p;}
}
int main(){char p[100];cin >> p;int len = 0;char* s = NULL;findNonRepeatStr(p, s, len);for (int i = 0; i < len; i++){cout << s[i];}cout << " :max length is "<<len<<", start from "<<s-p+1<<" char."<<endl;
}
更多推荐
查找最长不重复字串
发布评论