Mai intai trebuie sa te autentifici.
Cod sursa(job #1676564)
Utilizator | Data | 5 aprilie 2016 23:51:31 | |
---|---|---|---|
Problema | Potrivirea sirurilor | Scor | 14 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.97 kb |
#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)
v.pb(i-n);
}
fout<<v.size()<<'\n';
for(i=0;i<v.size();++i)
fout<<v[i]<<' ';
return 0;
}