Pagini recente » Arhiva de probleme | Rating Dumitrescu Iustin (iustindumi) | Sedinta 2008-11-25 | Profil dey44and | Cod sursa (job #1981187)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define FOR(i, to) for (int i = 0; i < (to); ++i)
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<pair<int, int> > vpi;
typedef pair<ll,ll> pll;
typedef vector<string> vs;
#define Nmax 2101010
int nx[Nmax];
string s1,s2;
vi ret;
void make() {
int k = -1; nx[0] = -1;
for(int i=1;i<sz(s1);++i) {
while(k >= 0 && s1[k+1] != s1[i]) k = nx[k];
if(s1[k+1] == s1[i]) ++k; nx[i] = k;
}
}
void match() {
int k=-1;
for(int i=0;i<sz(s2);++i) {
while(k >= 0 && s1[k+1] != s2[i]) k = nx[k];
if(s1[k+1] == s2[i]) ++k; if(k==sz(s1)-1) { k = nx[k]; ret.pb(i+1 - sz(s1));}
}
}
int main() {
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
cin.sync_with_stdio(false);
fin >> s1 >> s2;
make();
match();
fout << sz(ret) << endl;
FOR(i,min(1000,sz(ret))) {
fout << ret[i] << " ";
}
}