Pagini recente » Cod sursa (job #1853746) | Atasamentele paginii Clasament avram_iancu_preoji_bis | Atasamentele paginii Clasament creanga10-12 | Cod sursa (job #2200425) | Cod sursa (job #2040229)
#include <fstream>
#include <string>
using namespace std;
ofstream fout("strmatch.out");
ifstream fin("strmatch.in");
string s;
string s1;
int n;
int n1;
int l[2000010];
int a;
int sol[1010];
void makeSufix(){
l[0] = 0;
int k = -1;
for(int i = 1; i < n; i++){
k = l[i - 1] - 1;
while(s[k + 1] != s[i] && k > -1)
k = l[k] - 1;
if(s[k + 1] == s[i]){
k++;
}
l[i] = k + 1;
}
}
void kmp(){
int k = -1;
for(int i = 0; i < n1; i++){
while(s[k + 1] != s1[i] && k > -1)
k = l[k] - 1;
if(s[k + 1] == s1[i]){
k++;
}
if(k == n - 1){
sol[++a] = i - n + 1;
if(a == 1000){
break;
}
k = l[k] - 1;
}
}
fout << a << '\n';
for(int i = 1; i <= a; i++){
fout << sol[i] << ' ';
}
}
int main()
{
fin >> s;
n = s.size();
fin >> s1;
n1 = s1.size();
makeSufix();
kmp();
return 0;
}