Pagini recente » Cod sursa (job #2687025) | Cod sursa (job #2182738) | Cod sursa (job #2842690) | Cod sursa (job #294006) | Cod sursa (job #3202208)
#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)
#define Nmax 1000100
#define LMax 40
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;
string s1,s2;
int cnt = 0;
class Kmp {
private:
vi nx;
public:
Kmp(string &s1) {
nx.resize(sz(s1));
int k = -1; nx[0] = -1;
rep(i,1,sz(s1)) {
while(k >= 0 && s1[k+1] != s1[i]) k = nx[k];
if(s1[k+1] == s1[i]) ++k;
nx[i] = k;
}
}
vi match(string &s1, string &s2) {
vi ret;
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];
++cnt;
if(ret.size() < 1000) ret.pb(i-sz(s1)+1);
}
}
return ret;
}
};
int main() {
ifstream fin; fin.open ("strmatch.in");
ofstream fout; fout.open ("strmatch.out");
fin>>s1>>s2;
Kmp k(s1);
vi m = k.match(s1,s2);
fout<<cnt<<"\n";
for(auto x: m) {
fout<<x<<" ";
}
return 0;
}