Pagini recente » Cod sursa (job #967926) | Cod sursa (job #846565) | Cod sursa (job #1344633) | Cod sursa (job #1570851) | Cod sursa (job #2097179)
#include <bits/stdc++.h>
#define MAX 2000000
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
char A[MAX+5],B[MAX+5];
int n,m;
int LPS[MAX+5];
vector <int> V;
void citire(void)
{
fi>>A;
fi>>B;
n=strlen(B);
m=strlen(A);
}
void generare_lps(char P[])
{
/// calculeaza lungimile prefixelor care sunt si sufixe
LPS[0]=0;
// for(int i=1,j=0; i<m; i++)
// {
// if(P[i]==P[j])
// {
// LPS[i]=j+1;
// //i++;
// j++;
// }
// else
// {
// if(j==0)
// {
// LPS[i]=0;
// //i++;
// }
// else
// j=LPS[j-1];
// LPS[i] = j;
// }
// }
int j=0;
for(int i=1; i<m; i++)
{
while(j&&P[j+1]!=P[i])
j=LPS[j];
if(P[j+1]==P[i])
j++;
LPS[i]=j;
}
}
void KMP(char T[], char P[])
{
for(int i=0,j=0; i<n;)
{
if(T[i]==P[j])
{
i++;
j++;
}
if(j==m)
{
if(V.size()<1000)
V.push_back(i-m);
j=LPS[j-1];
}
if(i<n && T[i]!=P[j])
{
if(j!=0)
j=LPS[j-1];
else
i++;
}
}
}
void afisare(void)
{
fo<<V.size()<<"\n";
for(int i=0; i<V.size(); i++)
fo<<V[i]<<" ";
}
int main()
{
citire();
generare_lps(A);
KMP(B,A);
afisare();
fi.close();
fo.close();
return 0;
}