Pagini recente » Cod sursa (job #1238136) | Cod sursa (job #524) | Cod sursa (job #1804392) | Cod sursa (job #3168230) | Cod sursa (job #1980855)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[2000000+3],c[2000000+3];
int A,C,v[2000000+3],ok;
vector <int> results;
vector <int> resultsok;
void prefix_c(int n)
{
v[0]=-1;
for(int i=2,j=0;i<=n;v[i++]=++j)
{
while(j>=0&&c[i]!=c[j+1])
j=v[j];
}
}
void KMP(int n, int m)
{
int k=0;
for(int i=1,j=0;i<=n;i++,j++)
{
while(j>=0&&a[i]!=c[j+1])
j=v[j];
if(j+1==m)
{
k++;
results.push_back(i-m);
}
}
g<<k<<'\n';
for(int i=0;i<k;i++)
g<<results[i]<<" ";
}
int main()
{
f>>(c+1)>>(a+1);
A=strlen(a+1);
C=strlen(c+1);
prefix_c(C);
KMP(A,C);
return 0;
}