Approximate string matching technique has been widely applied to many fields such as network information retrieval, digital library, pattern recognition, text mining, IP routing searching, network intrusion detection, bioinformatics, and computing in musicology. The two concise parallel dynamic programming algorithms for approximate string matching with k-differences on CREW-PRAM (parallel random access machine with concurrent read and exclusive write) are presented by parallel computing the edition distance matrix D in the wave-front approach and by parallel computing the edition distance matrix D along the diagonal and horizontal directions, respectively. The first algorithm requires O(n) time and obtains a linear speedup by (m+1) processors. The second algorithm needs O(n/a+m) time in use of a(m+1) processors, where 1