در این مطلب، ویدئو طولانی ترین زیر رشته کاراکترهای تکرار شونده را در پایتون پیدا کنید با زیرنویس فارسی را برای دانلود قرار داده ام. شما میتوانید با پرداخت 15 هزار تومان ، این ویدیو به علاوه تمامی فیلم های سایت را دانلود کنید.اکثر فیلم های سایت به زبان انگلیسی می باشند. این ویدئو دارای زیرنویس فارسی ترجمه شده توسط هوش مصنوعی می باشد که میتوانید نمونه ای از آن را در قسمت پایانی این مطلب مشاهده کنید.
مدت زمان فیلم: 00:10:11
تصاویر این ویدئو:
قسمتی از زیرنویس این فیلم:
00:00:04,480 –> 00:00:07,569
[موسیقی]
2
00:00:09,040 –> 00:00:09,760
سلام به همه
3
00:00:09,760 –> 00:00:11,599
در این ویدیو، ما میخواهیم ببینیم که چگونه
4
00:00:11,599 –> 00:00:13,440
میتوانیم طولانیترین دنباله
5
00:00:13,440 –> 00:00:14,559
نویسههای تکرار شونده را
6
00:00:14,559 –> 00:00:17,359
در یک رشته پیدا کنیم، اگر چندین کاراکتر وجود داشته باشد، ما
7
00:00:17,359 –> 00:00:19,439
مجاز به چاپ هر یک از آنها
8
00:00:19,439 –> 00:00:22,720
به عنوان مثال هستیم.
9
00:00:22,720 –> 00:00:27,039
ببینید
10
00:00:27,039 –> 00:00:28,960
که طولانیترین دنباله نویسههای تکرار شونده
11
00:00:28,960 –> 00:00:30,480
در
12
00:00:30,480 –> 00:00:34,320
رشته aaa است، زیرا چهار a در یک
13
00:00:34,320 –> 00:00:35,120
ردیف
14
00:00:35,120 –> 00:00:36,800
وجود دارد، دنبالههای دیگری از
15
00:00:36,800 –> 00:00:39,360
نویسههای تکراری مانند bb در ابتدا
16
00:00:39,360 –> 00:00:42,480
و bbb در پایان وجود دارد، اما اینها به اندازهای
17
00:00:42,480 –> 00:00:44,559
که ما طولانیتر نیستند. به عنوان
18
00:00:44,559 –> 00:00:45,920
طولانی ترین انتخاب شده است،
19
00:00:45,920 –> 00:00:48,480
بنابراین چگونه می توانیم این چاه را پیدا کنیم، می توانیم بگوییم
20
00:00:48,480 –> 00:00:50,000
که می خواهیم در تمام
21
00:00:50,000 –> 00:00:51,600
طول های دنباله ممکن تکرار کنیم
22
00:00:51,600 –> 00:00:53,920
و برای هر طول دنباله ممکن
23
00:00:53,920 –> 00:00:55,039
آزمایش می کنیم تا ببینیم کدام
24
00:00:55,039 –> 00:00:56,719
دنباله های معتبر از
25
00:00:56,719 –> 00:00:58,559
شخصیت های تکراری هستند و از اینجا
26
00:00:58,559 –> 00:01:00,160
بزرگترین دنباله را پیدا می کنیم. در مورد
27
00:01:00,160 –> 00:01:02,239
تکرار کاراکترها، مشکل این
28
00:01:02,239 –> 00:01:02,800
29
00:01:02,800 –> 00:01:05,119
است که ما هم از طریق طول دنباله
30
00:01:05,119 –> 00:01:05,840
31
00:01:05,840 –> 00:01:07,600
و هم از طریق هر زیر رشته در
32
00:01:07,600 –> 00:01:10,479
رشته تکرار می کنیم و این می تواند زمان زیادی را ببرد.
33
00:01:10,479 –> 00:01:12,240
یک رویکرد خطی برای
34
00:01:12,240 –> 00:01:14,080
حل این مشکل در نظر بگیرید، به طوری که وقتی از یک
35
00:01:14,080 –> 00:01:14,720
کاراکتر
36
00:01:14,720 –> 00:01:17,439
بازدید می کنیم، دیگر آن را مشاهده نکنیم، ایده
37
00:01:17,439 –> 00:01:18,320
اصلی این الگوریتم این
38
00:01:18,320 –> 00:01:20,080
است که ما از یک
39
00:01:20,080 –> 00:01:22,479
پنجره کشویی استفاده می کنیم، باید متغیرهای کران پایین و بالایی داشته
40
00:01:22,479 –> 00:01:23,520
41
00:01:23,520 –> 00:01:25,360
باشیم و تکرار کنیم. کران بالا از
42
00:01:25,360 –> 00:01:26,720
ابتدا تا انتها
43
00:01:26,720 –> 00:01:29,119
همانطور که تکرار می کنیم، هر جفت کاراکترهای متوالی را با هم مقایسه می کنیم
44
00:01:29,119 –> 00:01:30,880
45
00:01:30,880 –> 00:01:32,560
اگر کاراکترها یکسان هستند، سپس
46
00:01:32,560 –> 00:01:34,560
اگر آنها متفاوت هستند ادامه می
47
00:01:34,560 –> 00:01:36,400
دهیم، سپس کل زیررشته را از
48
00:01:36,400 –> 00:01:37,840
جایی که کران پایینی خود را رها کردیم، می گیریم.
49
00:01:37,840 –> 00:01:40,000
جایی که کران بالایی ما
50
00:01:40,000 –> 00:01:41,040
در حال حاضر است
51
00:01:41,040 –> 00:01:42,880
و سپس کران پایین را
52
00:01:42,880 –> 00:01:45,520
به شروع زیر رشته احتمالی بعدی به روز می کنیم،
53
00:01:45,520 –> 00:01:47,520
بنابراین بیایید این مثال را در اینجا امتحان کنیم، فقط
54
00:01:47,520 –> 00:01:49,280
تمام کاراکترها را می نویسم
55
00:01:49,280 –> 00:01:52,320
و آنها را کمی فاصله می دهیم تا a b b a
56
00:01:52,320 –> 00:01:57,280
و سپس b خواهیم داشت. و سپس چهار a
57
00:01:57,280 –> 00:02:01,200
و سپس سه b و در نهایت یک
58
00:02:01,200 –> 00:02:04,479
a بنابراین
59
00:02:04,479 –> 00:02:08,479
با کران پایینی خود در صفر شروع می کنیم و
60
00:02:08,479 –> 00:02:10,160
کران بالایی خود را از طریق هر
61
00:02:10,160 –> 00:02:12,000
جفت کاراکترهای به هم پیوسته
62
00:02:12,000 –> 00:02:14,239
در اولین تکرار تکرار می کنیم که a و b را با هم مقایسه می کنیم
63
00:02:14,239 –> 00:02:15,040
64
00:02:15,040 –> 00:02:18,080
زیرا آنها هستند. مساوی نیست، ما می گوییم که
65
00:02:18,080 –> 00:02:19,520
بزرگترین دنباله فعلی ما از نویسه های تکرار شونده
66
00:02:19,520 –> 00:02:20,160
67
00:02:20,160 –> 00:02:23,520
a است و مرز پایین خود را به روز می کنیم تا
68
00:02:23,520 –> 00:02:25,200
از نمایه ای که به تازگی متوقف شده ایم شروع شود،
69
00:02:25,200 –> 00:02:26,879
بنابراین درست در اینجا
70
00:02:26,879 –> 00:02:30,319
خواهد بود، ما b را با b مقایسه می کنیم زیرا آنها همان هایی هستند
71
00:02:30,319 –> 00:02:31,760
که ما خود را حفظ می کنیم. مرز پایینتر
72
00:02:31,760 –> 00:02:32,959
جایی که هست
73
00:02:32,959 –> 00:02:36,080
و ما به حرکت ادامه میدهیم، بنابراین اکنون b را با a مقایسه میکنیم،
74
00:02:36,080 –> 00:02:38,319
بنابراین اکنون
75
00:02:38,319 –> 00:02:39,920
میگوییم که بزرگترین دنباله نویسههای تکراری فعلی ما
76
00:02:39,920 –> 00:02:41,440
77
00:02:41,440 –> 00:02:44,239
از شاخص یک به بالا اجرا میشود، اما
78
00:02:44,239 –> 00:02:45,120
شاخص
79
00:02:45,120 –> 00:02:48,000
سه را شامل نمیشود و پایینتر خود را بهروزرسانی میکنیم.
80
00:02:48,000 –> 00:02:49,680
مرز برای شروع بررسی یک زیررشته جدید،
81
00:02:49,680 –> 00:02:50,800
82
00:02:50,800 –> 00:02:55,680
بنابراین زیررشته نهایی فعلی ما bb است،
83
00:02:55,680 –> 00:02:57,680
بنابراین تا انتها ادامه می دهیم تا
84
00:02:57,680 –> 00:02:58,800
85
00:02:58,800 –> 00:03:00,560
ببینیم این دو بخشی
86
00:03:00,560 –> 00:03:01,920
از یک زیررشته نیستند و سپس ادامه
87
00:03:01,920 –> 00:03:02,400
می
88
00:03:02,400 –> 00:03:05,920
دهیم و می بینیم که این چهار رشته هستند. بنابراین aaa
89
00:03:05,920 –> 00:03:09,599
همه اینها در اینجا و بنابراین این در نهایت
90
00:03:09,599 –> 00:03:10,400
به
91
00:03:10,400 –> 00:03:14,239
a a a a به روز می شود و سپس می بینیم که
92
00:03:14,239 –> 00:03:18,319
b b b همه به هم متصل هستند
93
00:03:18,319 –> 00:03:22,159
و در نهایت با a پایان می دهیم و بنابراین
94
00:03:22,159 –> 00:03:25,680
می بینیم که aaa
95
00:03:25,680 –> 00:03:26,720
طولانی ترین رشته فرعی
96
00:03:26,720 –> 00:03:29,440
در پایان تکرار ما خواهد بود و هیچ
97
00:03:29,440 –> 00:03:31,120
ما فقط
98
00:03:31,120 –> 00:03:33,120
یک بار از آن عبور کردیم و مجبور نبودیم هیچ
99
00:03:33,120 –> 00:03:35,120
کاراکتری را بیش از یک بار بررسی کنیم،
100
00:03:35,120 –> 00:03:37,120
اساساً ایده این است که یک
101
00:03:37,120 –> 00:03:38,159
پنجره کشویی
102
00:03:38,159 –> 00:03:40,400
برای بررسی زیررشتهها ایجاد میکنیم و هر زمان که
103
00:03:40,400 –> 00:03:41,760
زیررشته ما دیگر
104
00:03:41,760 –> 00:03:43,920
از کاراکترهای تکرار شونده تشکیل نمیشود
105
00:03:43,920 –> 00:03:46,000
، رشته فرعی را قبل از آن مقایسه میکنیم. فقط
106
00:03:46,000 –> 00:03:48,480
به یکی که به عنوان پاسخ نهایی خود ذخیره کرده ایم تغییر داده
107
00:03:48,480 –> 00:03:49,840
108
00:03:49,840 –> 00:03:52,239
ایم و بررسی می کنیم که آیا طول آن بیشتر است یا نه
109
00:03:52,239 –> 00:03:54,000
قبل از اینکه به سراغ کد
110
00:03:54,000 –> 00:03:56,080
برویم، می توانیم به این نکته اشاره کنیم که الگوریتم ما می
111
00:03:56,080 –> 00:03:57,920
تواند سریعتر ساخته شود اگر
112
00:03:57,920 –> 00:04:00,239
این واقعیت را تصدیق کنیم که به محض مشاهده یک زیررشتههایی
113
00:04:00,239 –> 00:04:01,200
با طول معین،
114
00:04:01,200 –> 00:04:02,959
ما به دیدن زیررشتههای آینده با طولهای کمتر اهمیتی نمیدهیم،
115
00:04:02,959 –> 00:04:04,799
116
00:04:04,799 –> 00:04:08,799
بنابراین وقتی این bb را دقیقاً در اینجا
117
00:04:08,799 –> 00:04:11,120
دیدیم، فقط دنبال رشتههایی میگردیم
118
00:04:11,120 –> 00:04:12,080
که طول
119
00:04:12,080 –> 00:04:13,519
دو یا بیشتر دارند، به
120
00:04:13,519 –> 00:04:15,200
زیررشتههای با طول اهمیتی نمیدهیم. یکی به
121
00:04:15,200 –> 00:04:17,918
همین ترتیب وقتی aaa را دیدیم،
122
00:04:17,918 –> 00:04:19,680
فقط دنبال زیررشتههای آینده با
123
00:04:19,680 –> 00:04:20,798
طول چهار و بالاتر
124
00:04:20,798 –> 00:04:22,240
میگردیم، حتی میتوانیم ببینیم که فقط دنبال
125
00:04:22,240 –> 00:04:24,000
رشتههای فرعی آینده با طول پنج به
126
00:04:24,000 –> 00:04:24,639
بالا
127
00:04:24,639 –> 00:04:26,720
هستیم، زیرا ما در حال حاضر بزرگترین را داریم. e از
128
00:04:26,720 –> 00:04:28,880
طول چهار، بنابراین ما هیچ
129
00:04:28,880 –> 00:04:30,479
زیررشتهای را که
130
00:04:30,479 –> 00:04:32,000
کمتر از چهار کاراکتر کوچکتر یا مساوی
131
00:04:32,000 –> 00:04:34,320
چهار کاراکتر داشته باشد، در نظر نگیریم، مانند bbb،
132
00:04:34,320 –> 00:04:35,919
اکنون در حال کدنویسی این موضوع به
133
00:04:35,919 –> 00:04:38,000
عنوان تمرین برای شما بچهها در حال حاضر، ما
134
00:04:38,000 –> 00:04:39,600
فقط رویکرد سادهتری را در پیش خواهیم گرفت.
135
00:04:39,600 –> 00:04:42,160
بیایید ادامه دهیم و این را کدنویسی کنیم،
136
00:04:42,160 –> 00:04:43,280
بنابراین در اینجا
137
00:04:43,280 –> 00:04:45,840
ما الگوی کد خود را داریم، سربرگ تعریف تابع خود
138
00:04:45,840 –> 00:04:47,199
139
00:04:47,199 –> 00:04:48,560
را داریم، بنابراین ما آن را طولانیترین
140
00:04:48,560 –> 00:04:50,800
زیر رشته ماشینهای تکرار شونده مینامیم و
141
00:04:50,800 –> 00:04:52,320
یک رشته را به عنوان ورودی میگیریم
142
00:04:52,320 –> 00:04:54,720
و سپس اگر در خط نگاه کنید 6 من فقط
143
00:04:54,720 –> 00:04:56,240
از یک elias به نام
144
00:04:56,240 –> 00:04:58,320
funk استفاده می کنم تا به کارت های تکرار شونده زیر رشته ای طولانی اشاره کنم، به
145
00:04:58,320 –> 00:04:59,840
طوری که وقتی برای
146
00:04:59,840 –> 00:05:01,199
آزمایش کد خود می
147
00:05:01,199 –> 00:05:03,520
رویم، مجبور نباشیم هر بار کل
148
00:05:03,520 –> 0