Pagini recente » Rating Gheorghe Rares (123RaRes123) | Cod sursa (job #227970) | Cod sursa (job #402753) | Cod sursa (job #1279155) | Cod sursa (job #2999042)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int const N = 2e6 + 3;
int n , m;
char pat[N] , str[N];
int lps[N] , idx[N];
int main()
{
fin >> pat >> str;
n = strlen(str);
m = strlen(pat);
lps[0] = 0;
int j = 1 , i = 0;
while(j < m){
if(pat[i] != pat[j]){
if(!i){
++j;
}else
i = lps[i];
}else{
while(j < m && pat[i] == pat[j]){
++i;
lps[j++] = i;
}
}
}
int ap = 0;
i = 0 , j = 0;
while(i < n){
if(str[i] == pat[j]){
if(j == m - 1){
idx[ap++] = i - m + 1;
j = lps[j];
}else{
++i,++j;
}
}else{
if(j == 0){
++i;
}else{
j = lps[j];
}
}
}
fout << ap << '\n';
for(int i = 0 ; i < min(1000 , ap) ; ++ i)
fout << idx[i] << ' ';
fout << '\n';
return 0;
}