



'''simple docstring'''






import random
import unittest

from torch.utils.data import BatchSampler, DataLoader, IterableDataset

from accelerate import Accelerator
from accelerate.data_loader import (
    BatchSamplerShard,
    DataLoaderDispatcher,
    DataLoaderShard,
    IterableDatasetShard,
    SkipBatchSampler,
    SkipDataLoader,
    skip_first_batches,
)




class 	a__       (							lowercase__						):





							'''simple docstring'''






							def __init__(	self      ,					lowerCamelCase_=0.01      ,					lowerCamelCase_=10_00     ) ->							Optional[int]:
														lowerCAmelCase__      =			p_stop
														lowerCAmelCase__      =			max_length







							def __iter__(	self     ) ->							Dict:
														lowerCAmelCase__      =			0
														lowerCAmelCase__      =			False
														while not stop and count < self.max_length:
																					yield count
																					count += 1
																					lowerCAmelCase__      =			random.random() < self.p_stop




class 	a__       (							unittest.TestCase						):





							'''simple docstring'''






							def 						__SCREAMING_SNAKE_CASE							(	self      ,					lowerCamelCase_      ,					lowerCamelCase_      ,					lowerCamelCase_=False      ,					lowerCamelCase_=True     ) ->							List[Any]:
														lowerCAmelCase__      =			[
														    BatchSamplerShard(__lowercase      ,					2      ,					__lowercase      ,					split_batches=__lowercase      ,					even_batches=__lowercase     )
														    for i in range(2     )
														]
														lowerCAmelCase__      =			[list(__lowercase     ) for batch_sampler_shard in batch_sampler_shards]
														if not split_batches:
																					self.assertListEqual([len(__lowercase     ) for shard in batch_sampler_shards]      ,					[len(__lowercase     ) for e in expected]     )
														self.assertListEqual(__lowercase      ,					__lowercase     )







							def 						__SCREAMING_SNAKE_CASE							(	self     ) ->							Tuple:
														# Check the shards when the dataset is a round multiple of total batch size.
														lowerCAmelCase__      =			BatchSampler(range(24     )      ,					batch_size=3      ,					drop_last=__lowercase     )
														lowerCAmelCase__      =			[
														    [[0, 1, 2], [6, 7, 8], [12, 13, 14], [18, 19, 20]],
														    [[3, 4, 5], [9, 10, 11], [15, 16, 17], [21, 22, 23]],
														]
														self.check_batch_sampler_shards(__lowercase      ,					__lowercase     )

														lowerCAmelCase__      =			BatchSampler(range(24     )      ,					batch_size=3      ,					drop_last=__lowercase     )
														# Expected shouldn't change
														self.check_batch_sampler_shards(__lowercase      ,					__lowercase     )

														# Check the shards when the dataset is a round multiple of batch size but not total batch size.
														lowerCAmelCase__      =			BatchSampler(range(21     )      ,					batch_size=3      ,					drop_last=__lowercase     )
														lowerCAmelCase__      =			[
														    [[0, 1, 2], [6, 7, 8], [12, 13, 14], [18, 19, 20]],
														    [[3, 4, 5], [9, 10, 11], [15, 16, 17], [0, 1, 2]],
														]
														self.check_batch_sampler_shards(__lowercase      ,					__lowercase     )

														lowerCAmelCase__      =			BatchSampler(range(21     )      ,					batch_size=3      ,					drop_last=__lowercase     )
														lowerCAmelCase__      =			[
														    [[0, 1, 2], [6, 7, 8], [12, 13, 14]],
														    [[3, 4, 5], [9, 10, 11], [15, 16, 17]],
														]
														self.check_batch_sampler_shards(__lowercase      ,					__lowercase     )

														# Check the shards when the dataset is not a round multiple of batch size but has a multiple of
														# num_processes batch.
														lowerCAmelCase__      =			BatchSampler(range(22     )      ,					batch_size=3      ,					drop_last=__lowercase     )
														lowerCAmelCase__      =			[
														    [[0, 1, 2], [6, 7, 8], [12, 13, 14], [18, 19, 20]],
														    [[3, 4, 5], [9, 10, 11], [15, 16, 17], [21, 0, 1]],
														]
														self.check_batch_sampler_shards(__lowercase      ,					__lowercase     )

														lowerCAmelCase__      =			BatchSampler(range(22     )      ,					batch_size=3      ,					drop_last=__lowercase     )
														lowerCAmelCase__      =			[
														    [[0, 1, 2], [6, 7, 8], [12, 13, 14]],
														    [[3, 4, 5], [9, 10, 11], [15, 16, 17]],
														]
														self.check_batch_sampler_shards(__lowercase      ,					__lowercase     )

														# Check the shards when the dataset is not a round multiple of batch size but and has not a multiple of
														# num_processes batch.
														lowerCAmelCase__      =			BatchSampler(range(20     )      ,					batch_size=3      ,					drop_last=__lowercase     )
														lowerCAmelCase__      =			[
														    [[0, 1, 2], [6, 7, 8], [12, 13, 14], [18, 19, 0]],
														    [[3, 4, 5], [9, 10, 11], [15, 16, 17], [1, 2, 3]],
														]
														self.check_batch_sampler_shards(__lowercase      ,					__lowercase     )

														lowerCAmelCase__      =			BatchSampler(range(20     )      ,					batch_size=3      ,					drop_last=__lowercase     )
														lowerCAmelCase__      =			[
														    [[0, 1, 2], [6, 7, 8], [12, 13, 14]],
														    [[3, 4, 5], [9, 10, 11], [15, 16, 17]],
														]
														self.check_batch_sampler_shards(__lowercase      ,					__lowercase     )

														# Check the shards when the dataset is very small.
														lowerCAmelCase__      =			BatchSampler(range(2     )      ,					batch_size=3      ,					drop_last=__lowercase     )
														lowerCAmelCase__      =			[[[0, 1, 0]], [[1, 0, 1]]]
														self.check_batch_sampler_shards(__lowercase      ,					__lowercase     )

														lowerCAmelCase__      =			BatchSampler(range(2     )      ,					batch_size=3      ,					drop_last=__lowercase     )
														lowerCAmelCase__      =			[[], []]
														self.check_batch_sampler_shards(__lowercase      ,					__lowercase     )







							def 						__SCREAMING_SNAKE_CASE							(	self     ) ->							Optional[int]:
														# Check the shards when the dataset is a round multiple of batch size.
														lowerCAmelCase__      =			BatchSampler(range(24     )      ,					batch_size=4      ,					drop_last=__lowercase     )
														lowerCAmelCase__      =			[
														    [[0, 1], [4, 5], [8, 9], [12, 13], [16, 17], [20, 21]],
														    [[2, 3], [6, 7], [10, 11], [14, 15], [18, 19], [22, 23]],
														]
														self.check_batch_sampler_shards(__lowercase      ,					__lowercase      ,					split_batches=__lowercase     )

														lowerCAmelCase__      =			BatchSampler(range(24     )      ,					batch_size=4      ,					drop_last=__lowercase     )
														# Expected shouldn't change
														self.check_batch_sampler_shards(__lowercase      ,					__lowercase      ,					split_batches=__lowercase     )

														# Check the shards when the dataset is not a round multiple of batch size.
														lowerCAmelCase__      =			BatchSampler(range(22     )      ,					batch_size=4      ,					drop_last=__lowercase     )
														lowerCAmelCase__      =			[
														    [[0, 1], [4, 5], [8, 9], [12, 13], [16, 17], [20, 21]],
														    [[2, 3], [6, 7], [10, 11], [14, 15], [18, 19], [0, 1]],
														]
														self.check_batch_sampler_shards(__lowercase      ,					__lowercase      ,					split_batches=__lowercase     )

														lowerCAmelCase__      =			BatchSampler(range(22     )      ,					batch_size=4      ,					drop_last=__lowercase     )
														lowerCAmelCase__      =			[
														    [[0, 1], [4, 5], [8, 9], [12, 13], [16, 17]],
														    [[2, 3], [6, 7], [10, 11], [14, 15], [18, 19]],
														]
														self.check_batch_sampler_shards(__lowercase      ,					__lowercase      ,					split_batches=__lowercase     )

														# Check the shards when the dataset is not a round multiple of batch size or num_processes.
														lowerCAmelCase__      =			BatchSampler(range(21     )      ,					batch_size=4      ,					drop_last=__lowercase     )
														lowerCAmelCase__      =			[
														    [[0, 1], [4, 5], [8, 9], [12, 13], [16, 17], [20, 0]],
														    [[2, 3], [6, 7], [10, 11], [14, 15], [18, 19], [1, 2]],
														]
														self.check_batch_sampler_shards(__lowercase      ,					__lowercase      ,					split_batches=__lowercase     )

														lowerCAmelCase__      =			BatchSampler(range(21     )      ,					batch_size=4      ,					drop_last=__lowercase     )
														lowerCAmelCase__      =			[
														    [[0, 1], [4, 5], [8, 9], [12, 13], [16, 17]],
														    [[2, 3], [6, 7], [10, 11], [14, 15], [18, 19]],
														]
														self.check_batch_sampler_shards(__lowercase      ,					__lowercase      ,					split_batches=__lowercase     )

														# Check the shards when the dataset is very small.
														lowerCAmelCase__      =			BatchSampler(range(2     )      ,					batch_size=4      ,					drop_last=__lowercase     )
														lowerCAmelCase__      =			[[[0, 1]], [[0, 1]]]
														self.check_batch_sampler_shards(__lowercase      ,					__lowercase      ,					split_batches=__lowercase     )

														lowerCAmelCase__      =			BatchSampler(range(2     )      ,					batch_size=4      ,					drop_last=__lowercase     )
														lowerCAmelCase__      =			[[], []]
														self.check_batch_sampler_shards(__lowercase      ,					__lowercase      ,					split_batches=__lowercase     )







							def 						__SCREAMING_SNAKE_CASE							(	self     ) ->							List[str]:
														# Check the shards when the dataset is a round multiple of total batch size.
														lowerCAmelCase__      =			BatchSampler(range(24     )      ,					batch_size=3      ,					drop_last=__lowercase     )
														lowerCAmelCase__      =			[
														    [[0, 1, 2], [6, 7, 8], [12, 13, 14], [18, 19, 20]],
														    [[3, 4, 5], [9, 10, 11], [15, 16, 17], [21, 22, 23]],
														]
														self.check_batch_sampler_shards(__lowercase      ,					__lowercase      ,					even_batches=__lowercase     )

														lowerCAmelCase__      =			BatchSampler(range(24     )      ,					batch_size=3      ,					drop_last=__lowercase     )
														# Expected shouldn't change
														self.check_batch_sampler_shards(__lowercase      ,					__lowercase      ,					even_batches=__lowercase     )

														# Check the shards when the dataset is a round multiple of batch size but not total batch size.
														lowerCAmelCase__      =			BatchSampler(range(21     )      ,					batch_size=3      ,					drop_last=__lowercase     )
														lowerCAmelCase__      =			[
														    [[0, 1, 2], [6, 7, 8], [12, 13, 14], [18, 19, 20]],
														    [[3, 4, 5], [9, 10, 11], [15, 16, 17]],
														]
														self.check_batch_sampler_shards(__lowercase      ,					__lowercase      ,					even_batches=__lowercase     )

														lowerCAmelCase__      =			BatchSampler(range(21     )      ,					batch_size=3      ,					drop_last=__lowercase     )
														lowerCAmelCase__      =			[
														    [[0, 1, 2], [6, 7, 8], [12, 13, 14]],
														    [[3, 4, 5], [9, 10, 11], [15, 16, 17]],
														]
														self.check_batch_sampler_shards(__lowercase      ,					__lowercase      ,					even_batches=__lowercase     )

														# Check the shards when the dataset is not a round multiple of batch size but has a multiple of
														# num_processes batch.
														lowerCAmelCase__      =			BatchSampler(range(22     )      ,					batch_size=3      ,					drop_last=__lowercase     )
														lowerCAmelCase__      =			[
														    [[0, 1, 2], [6, 7, 8], [12, 13, 14], [18, 19, 20]],
														    [[3, 4, 5], [9, 10, 11], [15, 16, 17], [21]],
														]
														self.check_batch_sampler_shards(__lowercase      ,					__lowercase      ,					even_batches=__lowercase     )

														lowerCAmelCase__      =			BatchSampler(range(22     )      ,					batch_size=3      ,					drop_last=__lowercase     )
														lowerCAmelCase__      =			[
														    [[0, 1, 2], [6, 7, 8], [12, 13, 14]],
														    [[3, 4, 5], [9, 10, 11], [15, 16, 17]],
														]
														self.check_batch_sampler_shards(__lowercase      ,					__lowercase      ,					even_batches=__lowercase     )

														# Check the shards when the dataset is not a round multiple of batch size but and has not a multiple of
														# num_processes batch.
														lowerCAmelCase__      =			BatchSampler(range(20     )      ,					batch_size=3      ,					drop_last=__lowercase     )
														lowerCAmelCase__      =			[
														    [[0, 1, 2], [6, 7, 8], [12, 13, 14], [18, 19]],
														    [[3, 4, 5], [9, 10, 11], [15, 16, 17]],
														]
														self.check_batch_sampler_shards(__lowercase      ,					__lowercase      ,					even_batches=__lowercase     )

														lowerCAmelCase__      =			BatchSampler(range(20     )      ,					batch_size=3      ,					drop_last=__lowercase     )
														lowerCAmelCase__      =			[
														    [[0, 1, 2], [6, 7, 8], [12, 13, 14]],
														    [[3, 4, 5], [9, 10, 11], [15, 16, 17]],
														]
														self.check_batch_sampler_shards(__lowercase      ,					__lowercase      ,					even_batches=__lowercase     )

														# Check the shards when the dataset is very small.
														lowerCAmelCase__      =			BatchSampler(range(2     )      ,					batch_size=3      ,					drop_last=__lowercase     )
														lowerCAmelCase__      =			[[[0, 1]], []]
														self.check_batch_sampler_shards(__lowercase      ,					__lowercase      ,					even_batches=__lowercase     )

														lowerCAmelCase__      =			BatchSampler(range(2     )      ,					batch_size=3      ,					drop_last=__lowercase     )
														lowerCAmelCase__      =			[[], []]
														self.check_batch_sampler_shards(__lowercase      ,					__lowercase      ,					even_batches=__lowercase     )







							def 						__SCREAMING_SNAKE_CASE							(	self     ) ->							Dict:
														# Check the shards when the dataset is a round multiple of batch size.
														lowerCAmelCase__      =			BatchSampler(range(24     )      ,					batch_size=4      ,					drop_last=__lowercase     )
														lowerCAmelCase__      =			[
														    [[0, 1], [4, 5], [8, 9], [12, 13], [16, 17], [20, 21]],
														    [[2, 3], [6, 7], [10, 11], [14, 15], [18, 19], [22, 23]],
														]
														self.check_batch_sampler_shards(__lowercase      ,					__lowercase      ,					split_batches=__lowercase      ,					even_batches=__lowercase     )

														lowerCAmelCase__      =			BatchSampler(range(24     )      ,					batch_size=4      ,					drop_last=__lowercase     )
														# Expected shouldn't change
														self.check_batch_sampler_shards(__lowercase      ,					__lowercase      ,					split_batches=__lowercase      ,					even_batches=__lowercase     )

														# Check the shards when the dataset is not a round multiple of batch size.
														lowerCAmelCase__      =			BatchSampler(range(22     )      ,					batch_size=4      ,					drop_last=__lowercase     )
														lowerCAmelCase__      =			[
														    [[0, 1], [4, 5], [8, 9], [12, 13], [16, 17], [20, 21]],
														    [[2, 3], [6, 7], [10, 11], [14, 15], [18, 19]],
														]
														self.check_batch_sampler_shards(__lowercase      ,					__lowercase      ,					split_batches=__lowercase      ,					even_batches=__lowercase     )

														lowerCAmelCase__      =			BatchSampler(range(22     )      ,					batch_size=4      ,					drop_last=__lowercase     )
														lowerCAmelCase__      =			[
														    [[0, 1], [4, 5], [8, 9], [12, 13], [16, 17]],
														    [[2, 3], [6, 7], [10, 11], [14, 15], [18, 19]],
														]
														self.check_batch_sampler_shards(__lowercase      ,					__lowercase      ,					split_batches=__lowercase      ,					even_batches=__lowercase     )

														# Check the shards when the dataset is not a round multiple of batch size or num_processes.
														lowerCAmelCase__      =			BatchSampler(range(21     )      ,					batch_size=4      ,					drop_last=__lowercase     )
														lowerCAmelCase__      =			[
														    [[0, 1], [4, 5], [8, 9], [12, 13], [16, 17], [20]],
														    [[2, 3], [6, 7], [10, 11], [14, 15], [18, 19]],
														]
														self.check_batch_sampler_shards(__lowercase      ,					__lowercase      ,					split_batches=__lowercase      ,					even_batches=__lowercase     )

														lowerCAmelCase__      =			BatchSampler(range(21     )      ,					batch_size=4      ,					drop_last=__lowercase     )
														lowerCAmelCase__      =			[
														    [[0, 1], [4, 5], [8, 9], [12, 13], [16, 17]],
														    [[2, 3], [6, 7], [10, 11], [14, 15], [18, 19]],
														]
														self.check_batch_sampler_shards(__lowercase      ,					__lowercase      ,					split_batches=__lowercase      ,					even_batches=__lowercase     )

														# Check the shards when the dataset is very small.
														lowerCAmelCase__      =			BatchSampler(range(2     )      ,					batch_size=4      ,					drop_last=__lowercase     )
														lowerCAmelCase__      =			[[[0, 1]], []]
														self.check_batch_sampler_shards(__lowercase      ,					__lowercase      ,					split_batches=__lowercase      ,					even_batches=__lowercase     )

														lowerCAmelCase__      =			BatchSampler(range(2     )      ,					batch_size=4      ,					drop_last=__lowercase     )
														lowerCAmelCase__      =			[[], []]
														self.check_batch_sampler_shards(__lowercase      ,					__lowercase      ,					split_batches=__lowercase      ,					even_batches=__lowercase     )







							def 						__SCREAMING_SNAKE_CASE							(	self     ) ->							int:
														lowerCAmelCase__      =			[[0, 1, 2], [3, 4], [5, 6, 7, 8], [9, 10, 11], [12, 13]]
														lowerCAmelCase__      =			[BatchSamplerShard(__lowercase      ,					2      ,					__lowercase      ,					even_batches=__lowercase     ) for i in range(2     )]

														self.assertEqual(len(batch_sampler_shards[0]     )      ,					3     )
														self.assertEqual(len(batch_sampler_shards[1]     )      ,					2     )

														self.assertListEqual(list(batch_sampler_shards[0]     )      ,					[[0, 1, 2], [5, 6, 7, 8], [12, 13]]     )
														self.assertListEqual(list(batch_sampler_shards[1]     )      ,					[[3, 4], [9, 10, 11]]     )







							def 						__SCREAMING_SNAKE_CASE							(	self      ,					lowerCamelCase_      ,					lowerCamelCase_      ,					lowerCamelCase_      ,					lowerCamelCase_=False      ,					lowerCamelCase_=2      ,					lowerCamelCase_=False     ) ->							List[str]:
														random.seed(__lowercase     )
														lowerCAmelCase__      =			list(__lowercase     )

														lowerCAmelCase__      =			[
														    IterableDatasetShard(
														        __lowercase      ,					batch_size=__lowercase      ,					drop_last=__lowercase      ,					num_processes=__lowercase      ,					process_index=__lowercase      ,					split_batches=__lowercase      ,					)
														    for i in range(__lowercase     )
														]
														lowerCAmelCase__      =			[]
														for iterable_dataset_shard in iterable_dataset_shards:
																					# Since our random iterable dataset will be... random... we need to use a seed to get reproducible results.
																					random.seed(__lowercase     )
																					iterable_dataset_lists.append(list(__lowercase     )     )

														lowerCAmelCase__      =			batch_size // num_processes if split_batches else batch_size
														# All iterable dataset shard should have the same length, a round multiple of shard_batch_size
														lowerCAmelCase__      =			iterable_dataset_lists[0]
														for l in iterable_dataset_lists[1:]:
																					self.assertEqual(len(__lowercase     )      ,					len(__lowercase     )     )
																					self.assertTrue(len(__lowercase     ) % shard_batch_size == 0     )

														lowerCAmelCase__      =			[]
														for idx in range(0      ,					len(__lowercase     )      ,					__lowercase     ):
																					for l in iterable_dataset_lists:
																												observed += l[idx : idx + shard_batch_size]

														if not drop_last:
																					while len(__lowercase     ) < len(__lowercase     ):
																												reference += reference
														self.assertListEqual(__lowercase      ,					reference[: len(__lowercase     )]     )







							def 						__SCREAMING_SNAKE_CASE							(	self     ) ->							int:
														lowerCAmelCase__      =			42
														lowerCAmelCase__      =			RandomIterableDataset()

														self.check_iterable_dataset_shards(__lowercase      ,					__lowercase      ,					batch_size=4      ,					drop_last=__lowercase      ,					split_batches=__lowercase     )
														self.check_iterable_dataset_shards(__lowercase      ,					__lowercase      ,					batch_size=4      ,					drop_last=__lowercase      ,					split_batches=__lowercase     )
														self.check_iterable_dataset_shards(__lowercase      ,					__lowercase      ,					batch_size=4      ,					drop_last=__lowercase      ,					split_batches=__lowercase     )
														self.check_iterable_dataset_shards(__lowercase      ,					__lowercase      ,					batch_size=4      ,					drop_last=__lowercase      ,					split_batches=__lowercase     )

														# Edge case with a very small dataset
														lowerCAmelCase__      =			RandomIterableDataset(max_length=2     )

														self.check_iterable_dataset_shards(__lowercase      ,					__lowercase      ,					batch_size=4      ,					drop_last=__lowercase      ,					split_batches=__lowercase     )
														self.check_iterable_dataset_shards(__lowercase      ,					__lowercase      ,					batch_size=4      ,					drop_last=__lowercase      ,					split_batches=__lowercase     )
														self.check_iterable_dataset_shards(__lowercase      ,					__lowercase      ,					batch_size=4      ,					drop_last=__lowercase      ,					split_batches=__lowercase     )
														self.check_iterable_dataset_shards(__lowercase      ,					__lowercase      ,					batch_size=4      ,					drop_last=__lowercase      ,					split_batches=__lowercase     )







							def 						__SCREAMING_SNAKE_CASE							(	self     ) ->							Optional[Any]:
														lowerCAmelCase__      =			BatchSampler(range(16     )      ,					batch_size=4      ,					drop_last=__lowercase     )
														lowerCAmelCase__      =			SkipBatchSampler(__lowercase      ,					2     )
														self.assertListEqual(list(__lowercase     )      ,					[[8, 9, 10, 11], [12, 13, 14, 15]]     )







							def 						__SCREAMING_SNAKE_CASE							(	self     ) ->							Optional[int]:
														lowerCAmelCase__      =			SkipDataLoader(list(range(16     )     )      ,					batch_size=4      ,					skip_batches=2     )
														self.assertListEqual([t.tolist() for t in dataloader]      ,					[[8, 9, 10, 11], [12, 13, 14, 15]]     )







							def 						__SCREAMING_SNAKE_CASE							(	self     ) ->							Dict:
														lowerCAmelCase__      =			DataLoader(list(range(16     )     )      ,					batch_size=4     )
														lowerCAmelCase__      =			skip_first_batches(__lowercase      ,					num_batches=2     )
														self.assertListEqual([t.tolist() for t in new_dataloader]      ,					[[8, 9, 10, 11], [12, 13, 14, 15]]     )







							def 						__SCREAMING_SNAKE_CASE							(	self     ) ->							Tuple:
														lowerCAmelCase__      =			DataLoaderShard(list(range(16     )     )      ,					batch_size=4     )
														for idx, _ in enumerate(__lowercase     ):
																					self.assertEqual(dataloader.end_of_dataloader      ,					idx == 3     )

														# Test it also works on the second iteration
														for idx, _ in enumerate(__lowercase     ):
																					self.assertEqual(dataloader.end_of_dataloader      ,					idx == 3     )







							def 						__SCREAMING_SNAKE_CASE							(	self     ) ->							Any:
														Accelerator()
														lowerCAmelCase__      =			DataLoaderDispatcher(range(16     )      ,					batch_size=4     )
														for idx, _ in enumerate(__lowercase     ):
																					self.assertEqual(dataloader.end_of_dataloader      ,					idx == 3     )

														# Test it also works on the second iteration
														for idx, _ in enumerate(__lowercase     ):
																					self.assertEqual(dataloader.end_of_dataloader      ,					idx == 3     )



'''simple docstring'''






def       _snake_case     (  A				,					A )		->					bool:
							lowerCAmelCase__      =			len(A ) + 1
							lowerCAmelCase__      =			len(A ) + 1

							# dp is a 2d matrix where dp[i][j] denotes whether prefix string of
							# length i of input_string matches with prefix string of length j of
							# given pattern.
							# "dp" stands for dynamic programming.
							lowerCAmelCase__      =			[[0 for i in range(A )] for j in range(A )]

							# since string of zero length match pattern of zero length
							lowerCAmelCase__      =			1

							# since pattern of zero length will never match with string of non-zero length
							for i in range(1				,					A ):
														lowerCAmelCase__      =			0

							# since string of zero length will match with pattern where there
							# is at least one * alternatively
							for j in range(1				,					A ):
														lowerCAmelCase__      =			dp[0][j - 2] if pattern[j - 1] == '''*''' else 0

							# now using bottom-up approach to find for all remaining lengths
							for i in range(1				,					A ):
														for j in range(1				,					A ):
																					if input_string[i - 1] == pattern[j - 1] or pattern[j - 1] == ".":
																												lowerCAmelCase__      =			dp[i - 1][j - 1]

																					elif pattern[j - 1] == "*":
																												if dp[i][j - 2] == 1:
																																			lowerCAmelCase__      =			1
																												elif pattern[j - 2] in (input_string[i - 1], "."):
																																			lowerCAmelCase__      =			dp[i - 1][j]
																												else:
																																			lowerCAmelCase__      =			0
																					else:
																												lowerCAmelCase__      =			0

							return bool(dp[-1][-1] )


if __name__ == "__main__":
		import doctest

		doctest.testmod()
		# inputing the strings
		# input_string = input("input a string :")
		# pattern = input("input a pattern :")

		__UpperCAmelCase					       =							'''aab'''
		__UpperCAmelCase					       =							'''c*a*b'''

		# using function to check whether given string matches the given pattern
		if match_pattern(input_string, pattern):
				print(f"""{input_string} matches the given pattern {pattern}""")
		else:
				print(f"""{input_string} does not match with the given pattern {pattern}""")