Pagini recente » Cod sursa (job #358716) | Cod sursa (job #1039651) | Cod sursa (job #621998) | Cod sursa (job #1802054) | Cod sursa (job #3230153)
#include <fstream>
#include <cstring>
using namespace std;
const int Vmax = 2000001;
int n, m, sol[Vmax], pi[Vmax];
char a[Vmax], b[Vmax];
void Pi(){
int k = 0;
pi[1] = 0;
for(int i = 2; i <= n; i++){
while(k && a[k+1] != a[i]){
k = pi[k];
}
if(a[k+1] == a[i]){
++k;
}
pi[i] = k;
}
}
int main(){
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin >> (a+1) >> (b+1);
n = strlen(a+1);
m = strlen(b+1);
Pi();
int k = 0;
for(int i = 1; i <= m; i++){
while(k && a[k+1] != b[i]){
k = pi[k];
}
if(a[k+1] == b[i]){
++k;
}
if(k == n)
sol[++sol[0]] = i - n;
}
fout<<sol[0]<<'\n';
for(int i = 1; i <= sol[0] && i <= 1000; i++){
fout<<sol[i]<<" ";
}
return 0;
}