Pagini recente » Cod sursa (job #424447) | Cod sursa (job #897722) | Cod sursa (job #658418) | Cod sursa (job #643600) | Cod sursa (job #1628262)
#include <fstream>
#include <cstring>
#define DMAX 2000005
using namespace std;
char p[DMAX], s[DMAX];
int poz[DMAX], v[1002];
int lungs, lungp, k, ans;
int main()
{
ifstream in("strmatch.in");
ofstream out("strmatch.out");
in.get(p+1, DMAX);
in.get();
in.get(s+1, DMAX);
p[0] = '.'; s[0] = '.';
lungp= strlen(p) - 1; lungs = strlen(s) - 1;
k = 0;
for(int i = 2; i <= lungp; ++i){
while(p[i] != p[k+1] && k)
k = poz[k];
if(p[i] == p[k+1])
k++;
poz[i] = k;
}
k = 0;
if(s[1] == p[1])
k++;
for(int i = 2; i <= lungs; ++i){
while(s[i] != p[k+1] && k)
k = poz[k];
if(s[i] == p[k+1])
k++;
if(k == lungp){
ans++;
if(ans <= 1000){
v[ans] = i - lungp;
}
k = poz[k];
}
}
out<<ans<<"\n";
for(int i = 1; i <= ans && i <= 1000; ++i){
out<<v[i]<<" ";
}
out<<"\n";
in.close();
out.close();
return 0;
}