Pagini recente » Cod sursa (job #250080) | Cod sursa (job #977550) | Cod sursa (job #2111736) | Cod sursa (job #1067731) | Cod sursa (job #1301631)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
const int N = 2000010;
ifstream F("strmatch.in");
ofstream G("strmatch.out");
int n,m,pi[N];
char a[N],b[N];
void build(char a[],int n)
{
int p = 0;
for (int i=2;i<=n;++i)
{
while ( p > 0 && a[i] != a[p+1] )
p = pi[p];
if ( a[i] == a[p+1] )
p++;
pi[i] = p;
}
}
vector<int> match(char a[],int n,char b[],int m)
{
vector<int> ans;
int p = 0;
for (int i=1;i<=m;++i)
{
while ( p > 0 && b[i] != a[p+1] )
p = pi[p];
if ( b[i] == a[p+1] )
p++;
if ( p == n )
ans.push_back(i-n);
}
return ans;
}
int main()
{
F>>(a+1)>>(b+1);
n = strlen(a+1);
m = strlen(b+1);
build(a,n);
vector<int> ans = match(a,n,b,m);
G<<ans.size()<<'\n';
for (int i=0;i<int(ans.size()) && i<1000;++i)
G<<ans[i]<<' ';
G<<'\n';
}