1、从字符串A中找到匹配字符串B的第一个子串的位置，以下的代码经测试比Plauger的stl（VC7）中的
::std::string::find要快30%左右
// 仿函数版本
template < class Character = char, class Size = int >
struct StringFinder
{
typedef Size size_t;
typedef Character char_t;
size_t operator()( const char_t* lpszSource, const char_t* lpszSearch )
{
// maybe the processing of the following line can delay to the caller
if ( ( NULL == lpszSource ) || ( NULL == lpszSearch ) ) return -1;
const char_t& cSource = *lpszSource;
const char_t& cSearch = *lpszSearch;
for ( ; ; )
{
if ( 0 == *lpszSearch )
{
return ( lpszSource - ( lpszSearch - &cSearch ) - &cSource );
}
if ( 0 == *lpszSource ) return -1;
if ( *lpszSource != *lpszSearch )
{
lpszSource -= lpszSearch - &cSearch - 1;
lpszSearch = &cSearch;
continue;
}
++ lpszSource;
++ lpszSearch;
}
return -1;
}
};
// 函数版本
template < class char_t, class size_t >
size_t StringFind( const char_t* lpszSource, const char_t* lpszSearch )
{
// maybe the processing of the following line can delay to the caller
if ( ( NULL == lpszSource ) || ( NULL == lpszSearch ) ) return -1;
const char_t& cSource = *lpszSource;
const char_t& cSearch = *lpszSearch;
for ( ; ; )
{
if ( 0 == *lpszSearch )
{
return ( lpszSource - ( lpszSearch - &cSearch ) - &cSource );
}
if ( 0 == *lpszSource ) return -1;
if ( *lpszSource != *lpszSearch )
{
lpszSource -= lpszSearch - &cSearch - 1;
lpszSearch = &cSearch;
continue;
}
++ lpszSource;
++ lpszSearch;
}
return -1;
}
2、字符串比较，同strcmp的功能，以下为仿函数版本。
struct StringCmp
{
int operator()( const char* lpszStr1, const char* lpszStr2 )
{
if ( NULL == lpszStr1 )
{
if ( NULL == lpszStr2 ) return 0;
return -1;
}
if ( NULL == lpszStr2 ) return 1;
for ( ; ( 0 != ( ( *lpszStr1 ) & ( *lpszStr2 ) ) ); ++ lpszStr1, ++ lpszStr2 )
{
if ( *lpszStr1 < *lpszStr2 ) return -1;
if ( *lpszStr1 > *lpszStr2 ) return 1;
}
if ( 0 != *lpszStr2 ) return -1;
if ( 0 != *lpszStr1 ) return 1;
return 0;
}
};
3、快速排序算法（做了优化处理的），当元素总数不超过给定的阈值（threshold）时，采用插入排序，如果这个
做笔试题的话，个人认为难度偏大，因为其中程序部分可能技巧性比较强，需要很细心。俺也是花了很长时间上机
调试，我认为可能冒泡、插入排序更适合笔试。做完此题后，我还参读了Plauger's stl(VC7)中::std::sort
的源码，不同的是，其阈值默认为32，并且在超过阈值时也作了优化，小于或等于则都用了插入排序，呵呵。。。
struct NullType;
template < class T, class Iterator = T*, class Pr = NullType, class Diff = __int64, Diff threshold = 9 >
struct Sorter;
template < class T, class Iterator, class Diff, Diff threshold >
struct Sorter< T, Iterator, NullType, Diff, threshold >// sort by operator <
{
typedef T type;
typedef T& reference;
typedef const T& const_reference;
typedef T* pointer;
typedef Iterator iterator;
void operator()( iterator begin, iterator end )// sort in field [begin, end)
{
QuickSort( begin, end );
}
void InsertionSort( iterator begin, iterator end )// sort in field [begin, end)
{
type swap_temp;
for ( iterator i = begin + 1; i < end; ++ i )
{
for ( iterator j = i; ( j > begin ) && ( *j < *( j - 1 ) ); -- j )
{
swap_temp = *j;
j[0] = j[-1];
j[-1] = swap_temp;
}
}
}
void QuickSort( iterator begin, iterator end )// sort in field [begin, end)
{
Diff diff = end - begin;
// optimize speed with InsertionSort if the number of elements is not more than threshold
if ( threshold >= diff )
{
InsertionSort( begin, end );
return;
}
// find pivot
iterator pivot = begin + ( diff >> 1 );
// swap pivot with the element before end
type swap_temp;
swap_temp = end[-1];
end[-1] = *pivot;
pivot[0] = swap_temp;
// partition
iterator right_first = Partition( begin, end - 2, end[-1] );
// restore pivot to primary position
if ( right_first < ( end - 1 ) )
{
swap_temp = right_first[0];
right_first[0] = end[-1];
end[-1] = swap_temp;
}
if ( ( right_first - begin ) > 2 )
QuickSort( begin, right_first );// sort in field [begin, right_first)
if ( ( end - right_first ) > 3 )
QuickSort( right_first + 1, end );// sort in field [right_first + 1, end )
}
private:
iterator Partition( iterator first, iterator last, const_reference pivot )
{
iterator last_temp = last;
type swap_temp;
for ( ; first < last; )
{
if ( *last < pivot )
{
if ( *first < pivot )
{
++ first;
continue;
}
swap_temp = *first;
first[0] = *last;
last[0] = swap_temp;
++ first;
-- last;
}
else
{
if ( *first < pivot )
{
++ first;
-- last;
continue;
}
-- last;
continue;
}
}
// calculate the first position of right part
for ( ; ( !( pivot < *last ) )&& ( last <= last_temp ); ++ last ) {}
return last;
}
};
template < class T, class Iterator, class Pr, class Diff, Diff threshold >
struct Sorter< T, Iterator, Pr, Diff, threshold >// sort by Pr
{
// Just change it1 < it 2 to Pr( it1, it2 )
};
4、判断字符串是否为回环串，类似于"abcdcba"（？），这个可能挺简单，但是好像很多大公司出的
笔试题似乎都很简单，不知其考察点在于什么。。。
template < class Character = char >
struct IsCircleString
{
typedef Character char_t;
bool operator()( const char_t* pStr )
{
const char_t* pLast = pStr;
for ( ; 0 != *pLast; ++ pLast ) {}
if ( ( ( pLast - pStr ) & 0x1 ) == 0 ) return false;//偶数即返回false
-- pLast;
for ( ; pStr < pLast; ++ pStr, -- pLast )
{
if ( *pStr != *pLast ) return false;
}
return true;
}
};