Pagini recente » Cod sursa (job #1645767) | Cod sursa (job #1119063) | Cod sursa (job #2414508) | Cod sursa (job #388673) | Cod sursa (job #1676590)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <functional>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#define NMAX 2000005
#define MOD 666013
#define INF 0x3f3f3f3f
#define pb push_back
using namespace std;
typedef pair<int, int> pii;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[NMAX], b[NMAX];
int pref[NMAX], v[1005],n;
void prefix() {
int i,j=0;
for(i=2;i<=n;++i) {
while(j>0 && a[j+1] != a[i])
j=pref[j];
if(a[j+1]==a[i]) ++j;
pref[i]=j;
}
}
int main() {
int i,j,m,nr=0;
fin>>a+1>>b+1;
n=strlen(a+1);
m=strlen(b+1);
prefix();
for(i=1,j=0;i<=m;++i) {
while(j>0 && a[j+1] != b[i])
j=pref[j];
if(a[j+1] == b[i]) ++j;
if(j==n) {
j=pref[n];
++nr;
if(nr<=1000)
v[nr]=i-n;
}
}
fout<<nr<<'\n';
for(i=1;i<=min(1000,nr);++i)
fout<<v[i]<<' ';
return 0;
}