Pagini recente » Cod sursa (job #2491037) | Cod sursa (job #2659261) | Cod sursa (job #3245069) | Cod sursa (job #1953741) | Cod sursa (job #2999018)
#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[1001];
int main()
{
fin >> pat >> str;
n = strlen(str);
m = strlen(pat);
lps[0] = -1;
int j = 1 , i = 0;
while(j < m){
if(pat[i] == pat[j])
lps[j] = lps[i];
else{
lps[j] = i;
while(i >= 0 && pat[i] != pat[j])
i = lps[i];
}
++i , ++j;
}
lps[j] = i;
int ap = 0;
i = 0 , j = 0;
while(ap < 1000 && i < n){
if(str[i] == pat[j]){
++i , ++j;
if(j == m){
idx[++ap] = i - m;
j = lps[j];
}
}else{
j = lps[j];
if(j == -1){
++i , ++j;
}
}
}
fout << ap << '\n';
for(int i = 1 ; i <= ap ; ++ i)
fout << idx[i] << ' ';
fout << '\n';
return 0;
}