near_palindrome_checker.asm

near_palindrome_checker.asm

# $t0 = the first char address of the string
# $t1 = the last char address of the string
# $t2 = left iterator
# $t3 = right iterator
# $t4 = left iterator char
# $t5 = right iterator char
# $t7 = the character address to be omitted
#
# Emrehan Tüzün

.text

is_palindrome:	
	# $t0 = the first char address of the string
	la $t0, str
	
	# Prompt for the string
	la $a0, str_prompt
	li $v0, 4
	syscall
	
	# Take in the string
	li $v0, 8 
	la $a0, str
	li $a1, 100
	syscall

	# $t2 = temp iterator
	# $t3 = char
	move $t2, $t0

last_char_loop: 
	lbu $t3, ($t2)
	beq $t3, $0, end_of_string
	add $t2, $t2, 1
	j last_char_loop

end_of_string:
	# $t1 = the last char address of the string
	sub $t1, $t2, 2
	sub $t2, $t1, $t0

	# $t2 = left iterator
	# $t3 = right iterator
	move $t2, $t0
	move $t3, $t1
	
	# $t4 = left iterator char
	# $t5 = right iterator char
palindrome_check_loop:
	sle $t6, $t2, $t3
	beqz $t6, result_palindrome
	lbu $t4, ($t2)
	lbu $t5, ($t3)
	bne $t4, $t5, is_near_palindrome
	add $t2, $t2, 1
	sub $t3, $t3, 1
	j palindrome_check_loop

is_near_palindrome:
	# $t7 = the character address to be omitted
	# initially 0
	# updated unless all characters will be omitted
	move $t7, $t0
	
near_palindrome_check_loop:	
	# $t2 = left iterator
	# $t3 = right iterator
	move $t2, $t0
	move $t3, $t1

omit_check:
	beq $t7, $t2, omit_left_pointer
	beq $t7, $t3, omit_right_pointer
	j dont_omit

omit_left_pointer:
	add $t2, $t2, 1
	j dont_omit

omit_right_pointer:
	sub $t3, $t3, 1
	j dont_omit

dont_omit:
	sle $t6, $t2, $t3
	beqz $t6, result_near_palindrome
	lbu $t4, ($t2)
	lbu $t5, ($t3)
	bne $t4, $t5, omit_next
	add $t2, $t2, 1
	sub $t3, $t3, 1
	j omit_check

omit_next:
	sub $t6, $t7, 1
	beq $t6, $t1, result_not_palindrome 
	add $t7, $t7, 1
	j near_palindrome_check_loop

result_palindrome:
	la $a0, str_pal
	li $v0, 4
	syscall
	j exit

result_near_palindrome:
	la $a0, str_near_pal
	li $v0, 4
	syscall
	j exit
	
result_not_palindrome:
	la $a0, str_not_pal
	li $v0, 4
	syscall
	j exit
	
exit:
	li $v0, 10
	syscall

.data
str: 		.space 100
str_prompt: 	.asciiz "Please enter a string: "
str_pal:	.asciiz "That string is a palindrome :) \n"
str_near_pal:	.asciiz "That string is a near palindrome :| \n"
str_not_pal:	.asciiz "That string is not a palindrome :( \n"

near_palindrome_checker.md

Palindrome (& Near-Palindrome!) Checker

This is a fast and readable implementation for checking if a string is a palondrome or a near-palindrome¹ in MIPS Assembly.

[1] A string is a near-palindrome if removing one character makes it a palindrome.

Usage

Please enter a string: aibohphobia
That string is a palindrome :) 

Please enter a string: emre
That string is a near palindrome :| 

Please enter a string: palindrome
That string is not a palindrome :( 

Algorithm

Here is what the algorithm looks like in executable pseudo code:

Last char position calculation:

string = raw_input('Please enter a string: ')

last_pos = -1
for char in string:
	last_pos = last_pos + 1

Palindrome checker:

left_ptr = 0
right_ptr = last_pos
while (left_ptr < right_ptr):
	if (string[left_ptr] != string[right_ptr]):
		break
	left_ptr = left_ptr + 1
	right_ptr = right_ptr - 1

if (left_ptr >= right_ptr): 
	print 'That string is a palindrome :)'
	exit()

Near-palindrome checker:

for omit in range(last_pos + 1):
	left_ptr = 0
	right_ptr = last_pos
	while (left_ptr < right_ptr):
		if (omit == left_ptr):
			left_ptr = left_ptr + 1
		if (omit == right_ptr):
			right_ptr = right_ptr - 1
		if (string[left_ptr] != string[right_ptr]):
			break
		left_ptr = left_ptr + 1
		right_ptr = right_ptr - 1
	if (left_ptr >= right_ptr): 
		print 'That string is a near palindrome :|'
		exit() 

print 'That string is not a palindrome :('
exit()

Licence!

Copyright © 2000 Emrehan Tüzün

This work is free. You can redistribute it and/or modify it under the terms of the Do What The Fuck You Want To Public License, Version 2, as published by Sam Hocevar. See http://www.wtfpl.net/ for more details.