Pagini recente » Cod sursa (job #3271017) | Cod sursa (job #2337200) | Cod sursa (job #865739) | Cod sursa (job #1722744) | Cod sursa (job #1648447)
#include <fstream>
#include <cstring>
#include <algorithm>
#include <vector>
#define w 2000001
using namespace std;
char s1[w];char s2[w];
int n,m;
unsigned int pi[w];
vector <unsigned int> v;
void prefix()
{
pi[1]=0;int k=0,q;
for (q=2;q<=n;q++)
{
while ( k>0 && s1[k+1]!=s1[q] )
k=pi[k];
if (s1[k+1]==s1[q])k++;
pi[q]=k;
}
}
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char r[w];
f.get(s1,w,'\n');f.get();
f.get(s2,w,'\n');f.get();
n=strlen(s1);m=strlen(s2);
strcpy(r,s1);strcpy(s1+1,r);s1[0]='\0';
strcpy(r,s2);strcpy(s2+1,r);s2[0]='\0';
prefix();
unsigned int q,k=0;
for (q=1;q<=m;q++)
{
while (k>0 && s1[k+1]!=s2[q])
k=pi[k];
if (s1[k+1]==s2[q]) k++;
if (k==n)
{
v.push_back(q-n);
k=pi[k];
}
}
n=v.size();
g<<n<<'\n';
n=min(n,1000);
for (k=0;k<n;k++)
g<<v[k]<<' ';
g<<'\n';
f.close();
g.close();
return 0;
}