To establish a more effective string pattern matching algorithm, a new improved star identification algorithm taking angular distances between main star and neighbor stars as recognition characteristics is designed. A guide star catalogue is constructed,and the angular distance values between main star and neighbor stars are encoded to quantized codes; then each code in characteristic character strings is rearranged from small to large in sequence. A string length code is appended to the end of the string to improve search speed of guide star catalogue, and so far the main star’s neighbor pattern is finished. Finally, an improved string matching algorithm based on KMP is proposed to identify the corresponding matches to the measured star in the whole guide star patterns. The identification rate of this algorithm is greater than 97.38% when the Gauss noise of position error is 2 pixels. 1 250 star maps are identified randomly on Pentium 1.6 GHz PC,and the average identification time is 42.78 ms. This algorithm has rotation invariability, good robustness and synchronization. The catalogue storage content is only 149.4 kB,so it can offer a higher retrieval efficiency.