Pagini recente » Cod sursa (job #287205) | Cod sursa (job #1975173) | Cod sursa (job #1126177) | Cod sursa (job #706349) | Cod sursa (job #3230154)
#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");
char *p = a + 1;
char *q = b + 1;
fin >> p >> q;
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;
}