Pagini recente » Cod sursa (job #2566584) | Cod sursa (job #967905) | Cod sursa (job #2252951) | Cod sursa (job #3179162) | Cod sursa (job #3230151)
#include <fstream>
#include <cstring>
using namespace std;
const int Vmax = 2000001;
int n, m, sol[1001], 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 >> b;
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;
}