Cod sursa(job #1981185)

Utilizator Data 15 mai 2017 05:13:11 Potrivirea sirurilor 80 cpp done Arhiva educationala 1.21 kb
``````#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 101010
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() {
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
cin.sync_with_stdio(false);
cin >> s1 >> s2;
make();
match();
cout << sz(ret) << endl;
FOR(i,min(1000,sz(ret))) {
cout << ret[i] << " ";
}
}
``````