Pagini recente » Cod sursa (job #1058549) | Cod sursa (job #1328366) | Cod sursa (job #2799288) | Cod sursa (job #1521418) | Cod sursa (job #1676570)
#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],n;
vector<int> v;
int pref[NMAX];
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;
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];
v.pb(i-n);
}
}
fout<<v.size()<<'\n';
for(i=0;i<v.size();++i)
fout<<v[i]<<' ';
return 0;
}