Pagini recente » Cod sursa (job #1163821) | Cod sursa (job #439205) | Cod sursa (job #372141) | Cod sursa (job #533790) | Cod sursa (job #2040199)
#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++;
while(s[k] != s[i] && k > -1)
k = l[k] - 1;
l[i] = k + 1;
}
}
void kmp(){
int k = -1;
for(int i = 0; i < n1; i++){
k++;
while(s[k] != s1[i] && k > -1)
k = l[k] - 1;
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;
}